В некотором мире сейчас 31 декабря и все веселье только начинается. Снежик Сугробович слепил
N больших снежков и расположил их в ряд слева направо. На каждом
i-м снежке, если считать слева (1 <= i <= N), он написал целое число
ai. Он предлагает вам сыграть в игру. Снежик Сугробович разрешил сломать не более
N − 1 снежков по вашему выбору.
Допустим, осталось
K снежков. Снежик Сугробович будет удовлетворен и подарит вам хороший подарок, если для каждого целого числа
i (1<=i<=K) на
i-м снежке, если считать слева оставшиеся снежки, будет написано целое число
i.
Найдите минимальное количество снежков, которое вам нужно сломать, чтобы получить подарок. Если не получится, то выведите
-1.
Входные данные
В первой строке программа получает на вход целое число
N (1 <= N <= 200000). Во второй строке -
N натуральных чисел
ai (1<=ai<=N).
Выходные данные
Выведите минимальное количество снежков, которые нужно сломать, чтобы получить подарок, или выведите
-1, если это невозможно сделать.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
3
2 1 2 |
1 |
Сломайте первый снежок, числа на остальных снежках будут удовлетворять условию Снежика Сугробовича |
| 2 |
3
2 2 2 |
-1 |
|
| 3 |
10
3 1 4 1 5 9 2 6 5 3 |
7 |
|
| 4 |
1
1 |
0 |
|