Наибольшая упорядоченная подпоследовательность
Числовая последовательность a_i считается упорядоченной, если a_1 ≤ a_2 ≤ … ≤ a_N. Подпоследовательностью заданной числовой последовательности (a_1, a_2, …, a_N) называется произвольная последовательность (a_i1, a_i2, …, a_iK), где 1 ≤ i_1 < i_2 < … < i_K ≤ N. Например, последовательность (1, 7, 3, 5, 9, 4, 8) содержит упорядоченные подпоследовательности - например, (1, 7), (3, 4, 8) и другие. Все наибольшие упорядоченные подпоследовательности этой последовательности имеют длину 4, например (1, 3, 5, 8).
Для заданной числовой последовательности следует найти длину ее наибольшей упорядоченной подпоследовательности.
Входные данные
Первая строка содержит длину последовательности N (1 ≤ N ≤ 10^5). Вторая строка содержит элементы последовательности - N целых чисел, каждое из которых находится в интервале от 0 до 10^6.
Выходные данные
Вывести одно число - длину наибольшей упорядоченной подпоследовательности заданной последовательности.