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

При этом менять порядок ретрансляторов нельзя: можно только пропускать некоторые из них.

Требуется определить максимальное количество ретрансляторов, которое можно выбрать.

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

В первой строке записано одно целое число n — количество ретрансляторов.

Во второй строке записаны n целых чисел a1, a2, ..., an, где ai — уровень сигнала i-го ретранслятора.

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

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

Ограничения

• 1 <= n <= 2 * 10^5
• -10^9 <= ai <= 10^9

Пример 1

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

8
10 9 2 5 3 7 101 18

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

4

Пример 2

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

6
0 1 0 3 2 3

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

4

Пример 3

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

7
7 7 7 7 7 7 7

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

1

Пояснение

В первом примере можно выбрать, например, ретрансляторы с уровнями сигнала 2, 3, 7, 18. Их уровни идут строго по возрастанию, а длина такой последовательности равна 4.