Longest Decreasing Subsequence

Interview

Time limit1sMemory limit256 MB

Summary

Find the length of the longest strictly decreasing subsequence of the given sequence.

Level: Easy3 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

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.

Input

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$ ).

Output

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

Examples5

Example 1
Input
```
6
10 30 10 20 20 10
```
Expected output
```
3
```
Example 2
Input
```
1
1000
```
Expected output
```
1
```
Example 3
Input
```
5
7 7 7 7 7
```
Expected output
```
1
```
Example 4
Input
```
5
1 2 3 4 5
```
Expected output
```
1
```
Example 5
Input
```
5
5 4 3 2 1
```
Expected output
```
5
```