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