Мировой финансовый кризис - довольно серьезная тема. Некоторые люди бывают расслаблеными, а другие весьма обеспокоенными. Джон - один из них. Его очень беспокоит изменение состояния фондовой биржи. Он ежедневно следит за ценами на акции в поисках тенденций к росту. Для данной последовательности чисел p1, p2, ..., pn, представляющих цены на акции, восходящий тренд является подпоследовательностью pi1 < pi2 < ... < pik, с i1 < i2 < ... < ik. Задача Джона - найти самый длинный восходящий тренд.

Входные данные

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

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

Выходные данные

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

Пояснение

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