AlanashKO loves money. On the eve of the New Year he was given $N$ banknotes. Nominal value of each banknote is a positive integer. While playing, AlanashKO lay out all banknotes in a row and numbered them from the left to right from $1$ to $N$. Then he decided to sort all banknotes in nondecreasing order. For this AlanashKO doing following procedure: at first, he divides banknotes into one or more disjoint subsegments and each banknote belongs to some subsegment. Then, all subsegments in order from the left to right in turn are inserted into new row, i.e. at the first left-most subsegment (first subsegment) is inserted, then the next left-most inserted and so on. Each subsegment is inserted either between any two banknotes or at the one of the two ends of the current new row. The order of banknotes within the subsegment is not changed when inserted.

AlanashKO wants to minimize the number of subsegments so that he could finally sort the banknotes in nondecreasing order. Help him to find this value.

Input

The first line contains single positive integer $N$ ($1 \le N \le 10^6$) — the number of banknotes. The next line contains $N$ positive integers $a_i$ ($1 \le a_i \le 10^6$) — the value of $i$-th banknote.

Output

In the single line print single integer — the minimal number of subsegments allowing AlanashKO to sort banknotes.

Subtasks

This task includes four subtasks:

1. $N \le 8$. Score 9 points.
2. $N \le 20$. Score 16 points.
3. $N \le 300$. Score 20 points.
4. $N \le 10^6$. Score 55 points.

Each subtask will be scored only if the solution successfully passes all of the previous subtasks.

Examples

Input 1

6
3 6 4 5 1 2

Output 1

3

Note

Subsegment is consecutive sequence.

Let us consider sample test:

The minimal answer is division into 3 subsegments: |3 6|4 5|1 2| (sticks — subsgments borders)

After first step: initial row is |4 5|1 2|, new row is |3 6|.

On second step subsegment |4 5| inserted between $3$ and $6$.

After second step: initial row |1 2|, new row is: |3 4 5 6|.

Then, subsegment |1 2| inserted at the beginning of new row with a result |1 2 3 4 5 6|.