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