Вам надано масив, що містить ~n~ цілих чисел.

Ваше завдання — визначити найдовшу зростаючу підпослідовність у масиві, тобто найдовшу підпослідовність, де кожен елемент більший за попередній.

Підпослідовність — це послідовність, яку можна вивести з масиву шляхом видалення деяких елементів без зміни порядку елементів, що залишилися.

Обмеження

• ~1 \le n \le 2 \cdot 10^5~
• ~1 \le x_i \le 10^9~

Формат вхідних даних

Перший рядок містить ціле число ~n~: розмір масиву.

Після цього є ~n~ цілих чисел ~x_1,x_2,\ldots,x_n~: вміст масиву.

Формат вихідних даних

Виведіть довжину найдовшої зростаючої підпослідовності.

Приклад вхідних даних

8
7 3 5 3 6 2 9 8

Приклад вихідних даних

4