Longest Increasing Subsequence

Given a sequence $A$, write a program that finds the length of its longest increasing subsequence.

A subsequence of $A$ is what remains after deleting zero or more elements and keeping the rest in their original order. An increasing subsequence is one whose values grow strictly from left to right, so two elements with the same value cannot both be chosen.

For example, when $A = (10, 20, 10, 30, 20, 50)$, the longest increasing subsequence is 10, 20, 30, 50, and its length is 4.

The first line contains the size $N$ of the sequence $A$ ($1 \le N \le 1000$).

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

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