Uolevi has n cube blocks of different sizes s_1, s_2, \ldots, s_n. He is going to give them to Maija one at the time in that order. Maija forms towers from these blocks. Every time Maija gets a block from Uolevi, she can start a new tower from that block or place the block on top of an existing tower. To place the block on top of an existing tower, its size has to be smaller than the size of the current top block of the tower.

Maija wants to minimize the number of towers. Compute how many towers she will form if she acts optimally.

Input

The first line of input contains integer n, the number of blocks. The next line contains n integers, s_1, \ldots, s_n, the sizes of the blocks. The sizes are distinct.

Output

Output one integer, the smallest possible number of towers of blocks.

Constraints

• 1 \le n \le 1000
• 1 \le s_i \le 10^9

Examples

Input:

5
5 7 4 6 3

Output:

2

Input:

5
1 2 3 4 5

Output:

5