eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Фондовая биржа

Фондовая биржа

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Мировой финансовый кризис - довольно серьезная тема. Некоторые люди бывают расслаблеными, а другие весьма обеспокоенными. Джон - один из них. Его очень беспокоит изменение состояния фондовой биржи. Он ежедневно следит за ценами на акции в поисках тенденций к росту. Для данной последовательности чисел p_1, p_2, ..., p_n, представляющих цены на акции, восходящий тренд является подпоследовательностью p_{i_1} < p_{i_2} < ... < p_{i_k} с i_1 < i_2 < ... < i_k. Задача Джона — найти самый длинный восходящий тренд.

Вхідні дані

Каждый набор данных соответствует определенному набору курсов акций. Набор данных начинается с длины L~(L \le 10^5) последовательности чисел, за которыми следуют целые числа.

В любых местах входных данных могут встречаться пробелы. Входные данные верны и заканчиваются концом файла.

Вихідні дані

Выведите длину самого длинного восходящего тренда. Для каждого набора данных выведите ответ с новой строки.

Приклад

Состоит из трех тестов. В первом тесте длина L последовательности равна 6. Последовательность имеет вид: 5, 2, 1, 4, 5, 3. Длина самого длинного восходящего тренда равна 3.

Вхідні дані #1
6
5 2 1 4 5 3

3
1 1 1

4
4 3 2 1
Вихідні дані #1
3
1
1