Дана послідовність. Потрібно знайти довжину найбільшої зростаючої підпослідовності.

Формат вхідних даних

У стандартному потоці міститься число \(N\) - довжина послідовності \((1 ≤ N ≤ 1000)\). У другому рядку записана сама послідовність (через пропуск). Числа послідовності - цілі числа, не перевищують 10 000 по модулю.

Формат вихідних даних

У стандартний потік вивести найбільшу довжину зростаючої підпослідовності.

Приклад вхідних даних

6
3 29 5 5 28 6

Приклад вихідних даних

3