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