from bisect import bisect, bisect_left
from random import randint

task = '''
Дано:
    целое число 1<=n<=1E5 ( ОБРАТИТЕ ВНИМАНИЕ НА РАЗМЕРНОСТЬ! )
    массив A[1…n] натуральных чисел, не превосходящих 2E9.

Необходимо:
    Выведите максимальное 1<=k<=n, для которого гарантированно найдётся
    подпоследовательность индексов i[1]<i[2]<…<i[k] <= длины k,
    для которой каждый элемент A[i[k]] не больше любого предыдущего
    т.е. для всех 1<=j<k, A[i[j]]>=A[i[j+1]].

    В первой строке выведите её длину k,
    во второй - её индексы i[1]<i[2]<…<i[k]
    соблюдая A[i[1]]>=A[i[2]]>= ... >=A[i[n]].

    (индекс начинается с 1)

Решить задачу МЕТОДАМИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Время n*log(n)

    Sample Input:
    5
    5 3 4 4 2

    Sample Output:
    4
    1 3 4 5
'''


def getNotUpSeqIndexses(filename):
    # тут реализуйте логику задачи методами динамического программирования (!!!)
    # подумайте как стоит организовать динамику, чтобы получить решение за n log n
    # тесты не проверят скорость, а я проверю, и скорость и идею ;)
    # для корректной проверки рекомендуется сгенерировать тестовый файл размера 1E5
    # !!!!!!!!!!!!!!!!!!!!!!!!!     НАЧАЛО ЗАДАЧИ     !!!!!!!!!!!!!!!!!!!!!!!!!

    INF = int(2e10)  # будем считать это бесконечностью, т.к. на входе у нас числа < 2E9

    # считываем исходный массив
    s = open(filename).readlines()
    array = list(map(int, s[1].replace("\n", "").split(" ")))  # перепрыгиваем через 1-ю строку, читаем сразу 2-ю
    array.append(0)                         # когда массив перевернем, то индексация наших данных будет с 1. Очень удобно восстанавливать
    array = list(reversed(array))           # повернем данные так, чтобы использовать уже готовые bisect, bisect_left
    len_a = len(array)

    # инициализируем массив для динамики
    d = [-INF] + [INF] * len_a

    # ещё 2 массива нужны будут для восстановления, проинициализируем их нулями
    pos, pre = [0] * len_a, [0] * len_a

    for i in range(len_a):
        j = bisect(d, array[i])            # бинарный поиск на этот раз возьмем уже готовый, так код лаконичнее )
        if d[j - 1] <= array[i] < d[j]:    # мы развернули исходный массив, значит сейчас работаем с неубывающими элементами
            d[j] = array[i]                # критерий соблюдается, обновляем d[j]
            pos[j] = i                     # а также обновляем массивы для восстановления
            pre[i] = pos[j - 1]

    # восстанавливаем всё в res
    res = []
    i = pos[bisect_left(d, INF)-1]
    while i:
        res.append(len_a - i)              # результирующие индексы пойдут в нужном порядке (не в инвертированном)
        # res.append(array[i])             # debug. Выводим не индексы, а сами элементы. Так проще проконтролировать
        i = pre[i]

    print(len(res))
    return res
    # !!!!!!!!!!!!!!!!!!!!!!!!!     КОНЕЦ ЗАДАЧИ     !!!!!!!!!!!!!!!!!!!!!!!!!


def main():
    print ("Входные данные: dataC.txt из гита")
    filename = "dataC.txt"
    answer = getNotUpSeqIndexses(filename)
    for i in answer: print(i, end=" ")

    print("\n\nВходные данные: сгенерированный массив из 100000 случайных элементов")
    f = open('big_data.txt', 'w')
    f.write('100000' + '\n')

    for i in range(0, 99999):
        f.write(str(randint(1, 2E9)) + " ")
    f.write(str(randint(1, 2E9)) + "\n")
    f.close()
    filename = "big_data.txt"
    answer = getNotUpSeqIndexses(filename)
    for i in answer: print(i, end=" ")



# Для ручной проверки нажмите Ctrl+Shift+F10
# установив курсор на  main
# или создайте конфигурацию Run-Edit configuration
if __name__ == "__main__":
    main()
