Poisonous Plants

Source: HackerRank

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ plants from left to right, where plant $i$ has pesticide level $p_i$. After each day, every plant whose pesticide level is greater than that of the currently alive plant immediately to its left dies simultaneously. The process repeats on the surviving sequence. Determine the number of days until no plant dies.

Input

The first line contains $N$. The second line contains $N$ integers $p_1,p_2,\ldots,p_N$.

Output

Print the number of days until no more plants die.

Subtasks

• Subtask 1 (30 points): $N\le2000$; all other conditions are unchanged.
• Subtask 2 (70 points): $1\le N\le10^5$, $0\le p_i\le10^9$.

Examples

Input

7
6 5 8 4 7 10 9

Output

2

Explanation

Initially the pesticide levels are $[6,5,8,4,7,10,9]$.

On day $1$, each plant is compared with the alive plant immediately to its left using the state at the start of the day:

• $8>5$, so the plant with level $8$ dies;
• $7>4$, so the plant with level $7$ dies;
• $10>7$, so the plant with level $10$ dies.

After day $1$, the surviving sequence is $[6,5,4,9]$.

On day $2$, the plant with level $9$ is immediately to the right of level $4$, and $9>4$, so it dies. The survivors are $[6,5,4]$.

Now $6\ge5\ge4$, so no surviving plant has more pesticide than its left neighbor. The process stops after $2$ days, hence the output is 2.