Коллекционер расставил свои монеты в ряд в порядке, в котором они попали к нему в коллекцию. Для каждой монеты известна её ценность: у i-й монеты она равна a_i.

Он хочет оставить на витрине как можно больше монет так, чтобы:

• выбранные монеты шли в том же порядке, что и в исходном ряду;
• их ценности образовывали строго возрастающую последовательность.

Иными словами, нужно выбрать наибольшую по длине подпоследовательность монет, ценности которой строго возрастают.

Определите длину такой подпоследовательности.

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

Первая строка содержит одно целое число n — количество монет.

Вторая строка содержит n целых чисел a_i — ценности монет.

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

Выведите одно целое число — длину наибольшей строго возрастающей подпоследовательности.

Ограничения

• 1 <= n <= 2 * 10^5
• 1 <= a_i <= 10^9

Примеры

Пример 1

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

8
5 1 6 2 3 4 1 7

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

5

Пример 2

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

1
1

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

1