Задача: Снежик Сугробович - 2
В некотором мире сейчас 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 |
|
Ваш ответ: