Подъёмы Тянь-Шаня


Отправить решение Решать в редакторе

Сложность: 48%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Подъёмы Тянь-Шаня

Альпинист записал высоты n вершин хребта по порядку маршрута. Он хочет выбрать как можно больше вершин (не обязательно соседних, порядок сохраняется) так, чтобы каждая следующая была строго выше предыдущей. Сколько вершин можно выбрать?

Формат ввода

В первой строке записано n (1 ≤ n ≤ 10⁵). Во второй строке — n целых чисел hᵢ (1 ≤ hᵢ ≤ 10⁹).

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

Выведите длину наибольшей строго возрастающей подпоследовательности.

Пример 1

Вход:

6
5 2 8 6 3 9

Выход:

3

Пример 2

Вход:

4
7 7 7 7

Выход:

1

Комментарии

Еще нет ни одного комментария.