The Last Battle

The decisive battle between the Martians and humans is imminent. Human spies have discovered that the Martians have n fighters remaining. Similarly, the humans also have exactly n fighters left.

From previous battles, humans know that the i-th human can only defeat the Martian numbered i.

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 i-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 i-th human in the i-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 1.

Help the commander determine the minimum time required to rearrange the row so that the humans can win the decisive battle.

Input

The first line contains an integer n — the number of fighters on each side (1 ≤ n ≤ 2 * 10^5).

The second line contains n distinct integers a[1], a[2], ..., a[n], where a[i] is the number of the Martian that the fighter in the i-th position will face (1 ≤ a[i] ≤ n, and if i ≠ j, then a[i] ≠ a[j]).

Output

Output a single number k — 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 "-1".

Examples

Note

In the first example, the fighters initially face each other as follows:

Martians: 1 4 2 3 5

Humans: 1 2 3 4 5

The humans lose because Martians numbered 1 and 5 win their duels. After the first rearrangement, the lineup of fighters becomes:

Martians: 1 4 2 3 5

Humans: 5 1 2 3 4

Now, Martians 2 and 3 win their fights, so another rearrangement is necessary. After that, the lineup of fighters becomes such that all humans win their fights.

Martians: 1 4 2 3 5

Humans: 4 5 1 2 3