Фондовая биржа
Фондовая биржа
Мировой финансовый кризис - довольно серьезная тема. Некоторые люди бывают расслаблеными, а другие весьма обеспокоенными. Джон - один из них. Его очень беспокоит изменение состояния фондовой биржи. Он ежедневно следит за ценами на акции в поисках тенденций к росту. Для данной последовательности чисел 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.
6 5 2 1 4 5 3 3 1 1 1 4 4 3 2 1
3 1 1