Наибольшая возрастающая подпоследовательность

Условие

В первой строке дано n, во второй — n целых чисел. Выведите длину наибольшей строго возрастающей подпоследовательности. Элементы подпоследовательности не обязаны стоять подряд, но их порядок сохраняется.

Примеры

6
5 2 8 6 3 6

3

8
10 9 2 5 3 7 101 18

4

Ограничения

• 1 ≤ n ≤ 10^5
• -10^9 ≤ a_i ≤ 10^9