Mail.Ru Cup 2018 Раунд 1 |
---|
Закончено |
Изначально у Ильдара есть пустой массив. Он делает $$$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$$$, он получить не мог.
В третьем примере он мог получить $$$[0, 1, 2]$$$ без ошибок, но $$$239$$$ — явно ошибка.
Название |
---|