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