The Last Battle#8265
The decisive battle between the Martians and humans is imminent. Human spies have discovered that the Martians have fighters remaining. Similarly, the humans also have exactly fighters left.
From previous battles, humans know that the -th human can only defeat the Martian numbered .
The commander has decided to line up the humans in a row. Upon learning the Martians' strategy, the commander realized that the fighter in the -th position will face the Martian numbered a_i. The humans will only win if each of their fighters is guaranteed victory in their respective battles.
Initially, the commander placed the -th human in the -th position of the row. However, he soon realized that time is running out before the battle begins, and the humans might lose if the lineup remains unchanged. In one second, he can move the fighter from the last position to the front of the row; after this operation, they occupy the first position, and the position number of each of the other fighters increases by .
Help the commander determine the minimum time required to rearrange the row so that the humans can win the decisive battle.
The first line contains an integer — the number of fighters on each side (1 \le n \le 2 \cdot 10^5).
The second line contains distinct integers a_1, a_2, \ldots, a_n, where a_i is the number of the Martian that the fighter in the -th position will face (1 \le a_i \le n, and if i \ne j, then a_i \ne a_j).
Output a single number — the minimum number of seconds the commander needs to rearrange the row so that the humans win. If it is impossible for the humans to defeat the Martians, output .
Example 1
Example 2
In the first example, the fighters initially face each other as follows:
Martians:
Humans:
The humans lose because Martians numbered and win their duels. After the first rearrangement, the lineup of fighters becomes:
Martians:
Humans:
Now, Martians and win their fights, so another rearrangement is necessary. After that, the lineup of fighters becomes such that all humans win their fights.
Martians:
Humans: