B. Приписывание mex
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Изначально у Ильдара есть пустой массив. Он делает $$$n$$$ шагов. Каждый шаг состоит в том, что Ильдар выбирает некоторое подмножество элементов массива, полученного ранее, и приписывает в конец массива mex чисел этого подмножества.

Mex мультимножества чисел есть минимальное целое неотрицательное число, не содержащееся в массиве. Например, mex мультимножества чисел $$$[0, 2, 3]$$$ равен $$$1$$$, а mex мультимножества чисел $$$[1, 2, 1]$$$ равен $$$0$$$.

Более формально, на шаге с номером $$$m$$$, когда у Ильдара уже есть массив $$$a_1, a_2, \ldots, a_{m-1}$$$, он выбирает подмножество индексов $$$1 \leq i_1 < i_2 < \ldots < i_k < m$$$ (возможно, пустое), где $$$0 \leq k < m$$$, и записывает число $$$mex(a_{i_1}, a_{i_2}, \ldots a_{i_k})$$$ в конец массива.

После всех шагов он заметил, что мог ошибиться и записать какие-нибудь числа неправильно. Поэтому он простит вас определить по массиву $$$a_1, a_2, \ldots, a_n$$$ такой минимальный номер шага $$$t$$$, что он точно совершил ошибку на одном из шагов с номерами $$$1, 2, \ldots, t$$$, или определить, что он мог получить такой массив, не совершив ни одной ошибки.

Входные данные

В первой строке записано единственное целое число $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — количество шагов, которое сделал Ильдар.

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — массив, полученный Ильдаром.

Выходные данные

Если Ильдар мог так выбирать подмножества на каждом шаге, что в конце у него получится массив $$$a_1, a_2, \ldots, a_n$$$, выведите $$$-1$$$.

Иначе выведите одно целое число $$$t$$$ — такой минимальный номер шага, что он точно ошибся на одном из шагов $$$1, 2, \ldots, t$$$.

Примеры
Входные данные
4
0 1 2 1
Выходные данные
-1
Входные данные
3
1 0 1
Выходные данные
1
Входные данные
4
0 1 2 239
Выходные данные
4
Примечание

В первом примере Ильдар мог получить такой массив, не совершив ни одной ошибки. Вот как он мог это сделать:

  • $$$1$$$-й шаг. Изначальный массив пустой. Он может выбрать пустое подмножество изначального массива и получить число $$$0$$$, так как mex пустого массива равен $$$0$$$. Дописав это число в конец, он получит массив $$$[0]$$$.
  • $$$2$$$-й шаг. Сейчас массив $$$[0]$$$. Он может выбрать подмножество $$$[0]$$$ и получить число $$$1$$$, так как $$$mex(0) = 1$$$. Дописав это число в конец, он получит массив $$$[0,1]$$$.
  • $$$3$$$-й шаг. Сейчас массив $$$[0,1]$$$. Он может выбрать подмножество $$$[0,1]$$$ и получить число $$$2$$$, так как $$$mex(0,1) = 2$$$. Дописав это число в конец, он получит массив $$$[0,1,2]$$$.
  • $$$4$$$-й шаг. Сейчас массив $$$[0,1,2]$$$. Он может выбрать подмножество $$$[0]$$$ и получить число $$$1$$$, так как $$$mex(0) = 1$$$. Дописав это число в конец, он получит массив $$$[0,1,2,1]$$$.

Таким образом он сможет получить массив без ошибок, поэтому ответ $$$-1$$$.

Во втором тесте он точно совершит ошибку на первом шаге, так как ничего, кроме $$$0$$$, он получить не мог.

В третьем примере он мог получить $$$[0, 1, 2]$$$ без ошибок, но $$$239$$$ — явно ошибка.