The largest non-increasing subsequence. How to optimize an algorithm in Python?

Question

Python

Taking a course on algorithms at stepic.org
Stuck on the problem of finding the largest non-increasing subsequence in n log n time (see picture)

My solution passes all tests except the last one, 20th, giving the error Failed test #20 of 20. Time limit exceeded - it is clear that I do not pass by time, but I have been trying to understand why for a week now. And, as luck would have it, no one in the comments faced exactly such a problem, so I ask for help here.
I apologize in advance if the question is stupid, I'm still just learning and, unfortunately, I don't have any familiar programmers who I can turn to with questions (
A description of the algorithm for finding the largest increasing subsequence in time n log n using binary search is here:https://en.wikipedia.org/wiki/Longest_increasing_s...
I optimized this algorithm so that it builds not a strictly increasing subsequence, but a non-decreasing one and used it for an "inverted" input array, it works correctly on all tests .. maybe speed is lost somewhere else: for example, when displaying a result or creating lists.
Here is my code:

n = int(input())
x = list(map(int, input().split()))
x.reverse()
p = [0]*n
m = [0]*(n+1)
l = 0

for i in range(n):
    left = 1
    right = l
    while left <= right:
        mid = (left+right) // 2
        if x[m[mid]] < x[i]:
            left = mid+1
        elif x[m[mid]] == x[i]:
            left += 1
        else:
            right = mid-1
    new_l = left
    p[i] = m[new_l-1]
    
    if new_l > l:
        m[new_l] = i
        l = new_l 
    elif x[i] < x[m[new_l]]:
        m[new_l] = i
        
print(l)
k = m[l]
for i in range(l-1,-1,-1):
    print (n-k, end = '  ')
    k = p[k]

UPD. Thank you all very much for your advice and help! I found the error and corrected it, the decision was made, hurray!

Answer 1

To begin with, I recommend resending the solution, timeouts can happen simply due to a surge in load on the testing server.
If that doesn't help, then you really should optimize print, because Python has very expensive function calls, on my computer, these are the measurements I got:

l = list(range(10**5))

for i in l:  # 107 ms
    print(i, end=' ')

s = ' '.join(map(str, l))
print(s)  # 55 ms

In general, when debugging such problems, it makes sense to look for edge cases where your program will run the slowest - in this case, if I understood your program correctly (I didn’t read very carefully), this is a reverse-ordered array of size 10 ^ 5.
UPD: I found a bad input for your program - check it on an array where all values ​​are the same, the execution time turned out to be about 20 seconds on an array of length 10^4, I did not wait for a response at 10^5.
It happens because of these lines:

for i in range(n):
    left = 1 
    right = l 
...
    elif x[m[mid]] == x[i]:
        left += 1
...

In the worst case, you have O(n^2) here.
It seems that it will be enough just to change the loop to this one:

for i in range(n):
    left = 1
    right = l

    while left <= right:
        mid = (left+right) // 2
        if x[m[mid]] <= x[i]:
            left = mid+1
        else:
            right = mid-1
...

Answer 2

Madam, if this is really your code, then believe me, you have no problems and everything is in order. Many "programmers" will not even be able to understand what is written here. According to the subject, I’m too lazy to poke around in the task so deeply, but if the solution doesn’t work, then it’s not a fact that this is your problem, maybe the guys in the environment have too little timeout for executing tests. Speed ​​is most often lost on nested loops, you have one for with a nested while, while is a dangerous thing that can lead to infinite loops. Check your code so that it can't jump to infinite execution under certain conditions.