Числовая последовательность 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.
Вывести одно число - длину наибольшей упорядоченной подпоследовательности заданной последовательности.