Сума и произведение

Задача: Най-дълга нарастваща подредица

Дадена е редица от цели числа a_1, a_2, \ldots, a_n. Вашата задача е да намерите дължината на най-дългата строго нарастваща подредица в тази редица.

Строго нарастваща подредица е такава, в която всеки следващ елемент е по-голям от предходния.

Вход

• Първият ред съдържа едно цяло число $n$ (1 \leq n \leq 10^5) — броят на елементите в редицата.

• Вторият ред съдържа $n$ цели числа a_1, a_2, \ldots, a_n (-10^9 \leq a_i \leq 10^9) — елементите на редицата.

Изход

Изведете едно цяло число — дължината на най-дългата строго нарастваща подредица в дадената редица.

Пример

Вход

6
10 9 2 5 3 7 101 18

Изход

4

Забележка

В примера по-горе, една от най-дългите строго нарастващи подредици е [2, 3, 7, 101], която има дължина 4.