题目描述

It is known that $Ako\\,Kagari$ is not so good at using magic, that she even can't fly with broom. As the only witch without magic background in school, learning magic is a challenge to her and even the upcoming examinations have become her nightmare!

In a recent examination, she is given a sequence of balls $\\{Ball\\}$ with different numbers. Her teacher requires $Ako$ to paint the balls with the following rule :"For each of these $N$ balls, She has to choose a color and paint the ball with that color by a specific magic . If some balls are painted with the same color, each two balls have to satisfy the condition : $Ball_i < Ball_j (i< j)$".

Now, $Ako$ wants your help to count what is the minimum number of magical skills she has to practice.

输入格式

In the first line, you are given the number $N$($1 \\leq N \\leq 10^5$) .

In the second line, you are given the sequence of balls $\\{ Ball_1,Ball_2,\\cdots,Ball_n\\}$($0 \\leq Ball_i \\leq 10^9$) .

输出格式

Print the minimum number of magical skills $Ako$ has to practice .

样例

5 
2 1 4 5 3

2

5 
5 5 5 5 5

5

提示

In Sample1:

$Ako$ can pass the exam by, for example, painting $2$ and $3$ blue and painting $1$, $4$ and $5$ green. So she has to practice $2$ kinds of magical skills.

In Sample2:

All the balls have same number, so $Ako$ has to paint the $5$ balls with different color and practice $5$ kinds of magical skills.