Районная олимпиада по информатике 2017 года за 9 класс | Казахстанские олимпиады

Задача F. Массив

Вам дан массив $A$ длины $n$. Вы можете удалить некоторые элементы из него, при этом после всех удалении элементы должны стоять в строго возрастающем порядке. Выведите максимальную возможную длину массива после всех удалении.

Формат входного файла

Первая строка входного файла содержит целое число $N$ $(1 \le N \le 1000000)$ — длину последовательности. Вторая строка входного файла содержит $N$ целых чисел — элементы последовательности $A.$ Все элементы последовательности не превосходят 1000000000 по абсолютному значению.

Формат выходного файла

Выведите ответ к задаче.

Примеры

Вход

4
4 1 2 3

Выход

3