Box Packing

Interview

Time limit2sMemory limit512 MB

Summary

Given box sizes in order, find the longest subsequence where each box is strictly smaller than the next, counting boxes in the pile.

Level: Medium4 of 10
Topics: Dynamic programming, Binary search, Array, Greedy
Solved: No attempts yet

Problem

Yeongseon works part time at Namgyu's company, which is known for oversized packaging. Her job is to pack boxes inside one another.

The boxes stand in a row. An earlier box goes inside a later box only if the earlier box is smaller than the later one. A later box never goes inside an earlier box.

You are given the box sizes in order from the front. Following that rule, nest boxes one inside another and report the largest number of boxes that can end up in a single nested pile. The outermost box counts too.

Input

The first line contains the number of boxes $n$ ( $1 \le n \le 5000$ ).

The second line contains the box sizes $A_1, A_2, \dots, A_n$ in order from the front ( $1 \le A_i \le 100000$ ).

Output

Print the largest number of boxes that can be nested together under the rule.

Examples3

Example 1
Input
```
4
1 2 3 4
```
Expected output
```
4
```
Example 2
Input
```
4
4 3 3 1
```
Expected output
```
1
```
Example 3
Input
```
1
5
```
Expected output
```
1
```