Mingyun's Scheme

Mingyun enjoys teasing Junmin. Today he prepares $N$ cards, each with one integer written on it, and shows them to Junmin in a fixed order. Junmin picks as many cards as he likes, keeping the order in which they were shown, and hands that sequence back to Mingyun. If the sequence Junmin hands back is not strictly increasing, Mingyun calls him a fool. Strictly increasing means every value is smaller than the value right after it. When the cards shown are $4, 9, 10, 9$, picking $4, 9$ is safe, while $4, 10, 9$ or $9, 9$ gets Junmin teased.

Junmin never slipped up, so Mingyun added one more condition. The sequence Junmin hands back must be strictly increasing and must also have as many elements as possible. When the cards are $8, 9, 1, 2, 10$, picking $8, 9, 10$ or $1, 2, 10$ is safe, while $8, 9$ or $1, 2$ gets him teased.

Junmin decided to first work out how many elements such a sequence can have at most. For $8, 9, 1, 2, 10$ that number is $3$. Write a program that computes it for him.

The first line contains the number of cards $N$ ($1 \le N \le 1000$) that Mingyun shows.

The second line contains the $N$ integers written on the cards, in the order they are shown, separated by spaces. Each integer is between $1$ and $100{,}000{,}000$.

Print on the first line the maximum number of elements in a sequence Junmin can hand back.