In some world, it's December 31st and all the fun is just beginning. Snezhik Sugrobovich made
N large snowballs and arranged them in a row from left to right. On each
ith snowball, counting from the left (1 <= i <= N ), he wrote the integer
ai. He invites you to play a game. Snezhik Sugrobovich allowed to break no more than
N − 1 snowballs of your choice.
Let's say there are
K snowballs left. Snezhik Sugrobovich will be satisfied and give you a good gift if for each integer
i (1<=i<=K) on the
i-th snowball, counting the remaining snowballs on the left , an integer will be written
i.
Find the minimum number of snowballs you need to break in order to receive a gift. If it doesn't work, then print
-1.
Input
In the first line, the program receives an integer
N (1 <= N <= 200000) as input. In the second line -
N natural numbers
ai (1<=ai<=N).
Imprint
Print the minimum number of snowballs that need to be broken to get a present, or print
-1 if it's impossible.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
3
2 1 2
| 1 |
Break the first snowball, the numbers on the rest of the snowballs will satisfy Snezhik Sugrobovich's condition |
| 2 |
3
2 2 2
| -1 |
|
| 3 |
10
3 1 4 1 5 9 2 6 5 3
| 7 |
|
| 4 |
1
1 |
0 |
|