Дан массив \(A\), состоящий из \(N\) чисел. Найдите длину максимальной возрастающей подпоследовательности данного массива. Каждый элемент подпоследовательности должен быть строго больше предыдущего.

Например, \(A = [1, 5, 3, 2, 4]\), ответ \(3\), подходят \([1, 2, 4]\) либо \([1, 3, 4]\).

Входные данные

В первой строке дано число \(N\) \((1 \leq N \leq 10^5)\). Во второй строке дана массив \(A\) длины \(N\) \((1 \leq i \leq N, 1 \leq a_i \leq 10^5)\).

Выходные данные

Выведите единственное числа - ответ на задачу.

Примеры

Ввод 1

5
1 5 3 2 4

Ответ 1

3