How to optimize the algorithm?

Question

Python

My code solves the problem, but does not fit in time, it seems to work in n logn as it should. Perhaps I missed something in the binary search or in the conditions after exiting it. Now I think that the drawdown occurs with the same elements, i.e. I store both [5,4] and [5,4,4], although the first one is no longer needed and it slows down the search, you can delete it, but it's probably long, it's possible to replace None, but I haven't figured out how yet.

from array import array


def b_search3(xs, q):
    l, h = 0, len(xs)-1
    while l < h:
        mid = (l + h+1)//2
        if q > xs[mid]:
            h = mid -1
        else:
            l = mid
    return h


def max_sequence(l):
    temp = list()
    temp.append(array('i', (l[0],)))
    for i, v in enumerate(l[1:]):
        current = b_search3(tuple(x[-1] for x in temp), v)
        if v > temp[current][-1]:
            temp[current][-1] = v
        else:
            new = temp[current] + array('i', (v,))
            if len(new) > len(temp):
                    temp.append(new)
            elif v > temp[len(new)-1][-1]:
                temp[len(new)-1] = new
    answer = []
    prev = 0
    for el in temp[-1]:
        prev += l[prev:].index(el) +1
        answer.append(str(prev))
    return '\n'.join((str(len(temp[-1])), ' '.join(answer)))


def main():
    import sys
    reader = (map(int, line.split()) for line in sys.stdin)
    next(reader)
    l = array('i')
    l.fromlist(list(next(reader)))
    print(max_sequence(l))

if __name__ == '__main__':
    main()

Condition:
Given an integer 1≤n≤10^5 and an array A[1…n]A[1…n] containing non-negative integers not exceeding 10^9. Find the largest nonincreasing subsequence in A. On the first line print its length k, on the second line print its indices 1≤i1

Answer 1

I can't understand your code, I don't know Python
If for each element A[I] we store L[I] - the length of max. subsequence starting from it and P[I] is the index of the next element in it, then
L[I]=max L[J] : J>I, A[J]<=A[I], complexity O(N^2)