Problem Description

You are the guide for the DISCO presents Discovery Channel Programming Contest 2016 Finals' internal tour at DISCO.

There are $N$ rooms to be guided during the internal tour, each room is numbered from $1$ to $N$. The building's structure is circular, meaning you can move from room $i$ (for $1 \leq i \leq N-1$) to room $i+1$, and from room $N$ to room $1$. These paths are one-way only, and you cannot move in the opposite direction.

When in room $i$, you can either tour the room or move to the next room. However, to avoid boredom, each room can only be toured once. You know from experience that the fun factor of touring room $i$ is represented by an integer $A_i$.

The internal tour must start from room $1$ and end in room $1$ after all rooms have been toured. To ensure participants enjoy the tour, you decided to guide the rooms such that the fun factors of the toured rooms form a non-decreasing sequence when arranged in the order of touring. How many minimum laps around the building are needed to conduct the tour under these constraints?

A sequence $a$ of $n$ terms is called non-decreasing if $a_1 \leq a_2 \leq ... \leq a_n$. Moving from room $1$, visiting all rooms once, and returning to room $1$ is considered one lap around the building.

Input Format

The input is given from the standard input in the following format:

$N$ $A_1$ $A_2$ ... $A_N$

• The first line contains the number of rooms to be guided, $N$ ($2 \leq N \leq 10^5$).
• The second line contains the fun factors of each room represented by integers $A_i$ ($1 \leq A_i \leq 10^5$), separated by spaces.

Output Format

Output the minimum number of laps needed to conduct the internal tour satisfying the given conditions in one line. Do not forget the newline at the end.

Sample Input and Output

Sample Input #1

5
1 4 3 2 5

Sample Output #1

3

Sample Input #2

5
1 2 3 4 5

Sample Output #2

1

Sample Input #3

5
5 1 2 3 4

Sample Output #3

1

Sample Input #4

8
1 1 1 2 2 2 3 3

Sample Output #4

1

Notes/Hints

Partial Points

This problem has partial points.

• Correct answer for datasets satisfying $2 \leq N \leq 100$ will award $20$ points.
• Correct answer for datasets where $1 \leq A_i \leq N$ and $A_i \neq A_j$ for $i \neq j$ will award an additional $10$ points.
• Correct answer for datasets without additional constraints will award an additional $70$ points.

Sample Explanation 1

• It is possible to finish the tour in $3$ laps by touring in the following order: - In the first lap, tour room $1$ and room $4$. - In the second lap, tour room $3$. - In the third lap, tour room $2$ and room $5$. - Note that the tour must end in room $1$ after all rooms have been toured. - This case satisfies the first and second partial point conditions.

Sample Explanation 2

• It is possible to tour all rooms in one lap. - This case satisfies the first and second partial point conditions.

Sample Explanation 3

• It is possible to finish the tour in one lap by touring room $1$ last. - This case satisfies the first and second partial point conditions.

Sample Explanation 4

• Note that some room fun factors are duplicated. - This case satisfies the first partial point condition but not the second.

见题面 Input 部分

见题面 Output 部分