Найбільша впорядкована підпослідовність#2649
Числова послідовність a_i називається впорядкованою, якщо a_1 \leq a_2 \leq \dots \leq a_N. Підпослідовністю заданої числової послідовності (a_1, a_2, \dots, a_N) називається будь-яка послідовність (a_{i_1}, a_{i_2}, \dots, a_{i_K}), де 1 \leq i_1 < i_2 < \dots < i_K \leq N. Наприклад, послідовність (1, 7, 3, 5, 9, 4, 8) містить впорядковані підпослідовності, такі як , (3, 4, 8) тощо. Усі найдовші впорядковані підпослідовності цієї послідовності мають довжину , наприклад (1, 3, 5, 8).
Дано числову послідовність. Знайдіть довжину її найдовшої впорядкованої підпослідовності.
Перший рядок містить довжину послідовності (1 \leq N \leq 10^5). Другий рядок містить елементи послідовності — цілих чисел, кожне з яких перебуває в діапазоні від до 10^6.
Виведіть одне ціле число — довжину найдовшої впорядкованої підпослідовності заданої послідовності.
Приклад 1