Card Pickup Game

Interview

Time limit1sMemory limit128 MB

Summary

Simulate removing cards 1..N in order from a circular scan of a row, counting how many times the search wraps past the right end.

Level: Medium4 of 10
Topics: Queue, Simulation, Implementation
Solved: No attempts yet

Problem

Donghyun has N cards in a row. The cards contain the distinct integers from 1 to N.

At first, he scans the row from left to right until he finds the card numbered 1, then removes it. Next, starting from the position where that card was removed, he scans to the right until he finds the card numbered 2. After removing card 2, he continues in the same way to find card 3, and repeats this process until every card has been removed.

If he reaches the right end of the row before finding the next card, he claps once and resumes the search from the left end.

Given the initial order of the cards, compute how many times Donghyun claps before the game ends.

Input

The first line contains the number of cards, N.

Each of the next N lines contains one card number, in the initial order from left to right.

The card numbers are the integers from 1 to N, and each number appears exactly once.

1 ≤ N ≤ 100000

Output

Print one integer: the number of times Donghyun claps before the game ends.

Examples3

Example 1
Input
```
5
3
5
1
4
2
```
Expected output
```
2
```
Example 2
Input
```
3
2
1
3
```
Expected output
```
1
```
Example 3
Input
```
7
3
6
7
1
5
4
2
```
Expected output
```
3
```