The MaratonIME members like to have fun. As they enjoy having fun so much, they have invented a game named "Cîrokime". The game works as follows:
First, n cups with _Cîroc_1 are lined up. In front of the i-th cup a number ai is written. It is guaranteed that ai < ai + 1, for all 1 ≤ i < n. Then, the numbers are covered and the game starts.
The player must then find the cup that has a certain number x. It is guaranteed that this cup exists. For this, he has to choose a cup i and drink the beverage. Then, the cup's number ai is revealed and if this number is equal to x the game finished. Otherwise, the player has to choose another cup and so on.
"Cîrokime" is a traditional game among MaratonIME members, they play it every party. At the last party, Sussu had to drink all of the n cups because he found the right cup only at the end. He got sick for drinking so much and had to be carried home3
However, the DESMAME4 is scheduled for May 13 and Sussu wants to restore his dignity. For this, he wants to know, in the worst case, what is the maximum number of cups that he will have to drink if he plays in the optimal way.
The first line has a single integer n, the number of cups. The second line has n integers ai, the values hidden in each cup.
The output has a single line with a single integer: the minimum number of cups that Sussu should drink, in the worst case, if he plays in the optimal way.
1: Cîroc is a vodka brand made in France, known by its high sales price in market2
2: Balalaika also works
3: Based on real facts
4: Pre-BIFE5 party
5: University games that IME6 attends
6: Institute of Mathematics and Statistics
## Input
The first line has a single integer n, the number of cups. The second line has n integers ai, the values hidden in each cup. 1 ≤ n ≤ 105 For all i, 1 ≤ ai ≤ 109 For i < n, ai < ai + 1
## Output
The output has a single line with a single integer: the minimum number of cups that Sussu should drink, in the worst case, if he plays in the optimal way.
[samples]
## Note
1: Cîroc is a vodka brand made in France, known by its high sales price in market22: Balalaika also works3: Based on real facts4: Pre-BIFE5 party5: University games that IME6 attends6: Institute of Mathematics and Statistics
**Definitions**
Let $ R, C \in \mathbb{Z}^+ $ with $ 1 \leq R, C \leq 25 $.
Let $ DP \in \mathbb{Z}^{(R+1) \times (C+1)} $ be a 2D array such that:
- $ DP[0][j] = 0 $ for all $ j \in \{0, \dots, C\} $,
- $ DP[i][0] = 0 $ for all $ i \in \{0, \dots, R\} $,
- For $ i \in \{1, \dots, R\} $, $ j \in \{1, \dots, C\} $:
$$
DP[i][j] =
\begin{cases}
DP[i-1][j-1] + 1 & \text{if } A[i] = B[j], \\
\max(DP[i-1][j], DP[i][j-1]) & \text{otherwise}.
\end{cases}
$$
**Constraints**
1. $ DP $ is generated by the standard LCS algorithm on two strings $ A $ and $ B $ over the alphabet $ \{a, b, \dots, z\} $.
2. $ |A| = R $, $ |B| = C $.
**Objective**
Reconstruct any pair of strings $ A = a_1 a_2 \dots a_R $ and $ B = b_1 b_2 \dots b_C $, where $ a_i, b_j \in \{a, \dots, z\} $, such that the LCS table produced by the algorithm matches the given $ DP $.