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

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

Ограничение по времени Ограничение по памяти
2 секунда 64 мегабайта

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

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

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

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

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

Примеры

Вход

4
4 1 2 3

Выход

3