J

J. Путешествие

Гоша решил отправиться в турне по островам Алгосского архипелага. Туристическая программа состоит из последовательного посещения n достопримечательностей. У i-й достопримечательности есть свой рейтинг r_i. Впечатление от i-й достопримечательности равно её рейтингу r_i. Гоша хочет, чтобы его впечатление от каждой новой посещённой достопримечательности было сильнее, чем от предыдущей. Ради этого он даже готов пропустить некоторые места в маршруте –— в случае, если они нарушают этот порядок плавного возрастания. Помогите Гоше и найдите наибольшую возрастающую подпоследовательность в массиве рейтингов r_i.

Формат ввода

В первой строке дано натуральное число n (1 ≤ n ≤ 3 ⋅ 10³) –— сколько различных туристических мест есть в программе. Во второй строке дано n натуральных чисел через пробел –— рейтинги этих достопримечательностей ri (1 ≤ r_i ≤ 10⁹).

Формат вывода

Сначала в отдельной строке выведите длину найденной подпоследовательности. В следующей строке выведите номера достопримечательностей, которые образуют эту подпоследовательность.

Пример 1

5 4 2 9 1 13

3 1 3 5

Пример 2

6 1 2 4 8 16 32

6 1 2 3 4 5 6