Longest Decreasing Subsequence

A sequence $A$ is given. Write a program that finds the length of the longest decreasing subsequence of $A$.

A subsequence is formed by picking one or more elements of $A$ and keeping their original order. A decreasing subsequence is one in which every element is strictly greater than the element right after it.

For example, if $A = \{10, 30, 10, 20, 20, 10\}$, the longest decreasing subsequence is $\{30, 20, 10\}$ and its length is 3.

The first line contains the size $N$ of the sequence $A$ ($1 \le N \le 1{,}000$).

The second line contains $A_1, A_2, \dots, A_N$ separated by spaces ($1 \le A_i \le 1{,}000$).

Print the length of the longest decreasing subsequence of $A$ on the first line.