Изначально у Ильдара есть пустой массив. Он делает \(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\), или определить, что он мог получить такой массив, не совершив ни одной ошибки.
Выходные данные
Если Ильдар мог так выбирать подмножества на каждом шаге, что в конце у него получится массив \(a_1, a_2, \ldots, a_n\), выведите \(-1\).
Иначе выведите одно целое число \(t\) — такой минимальный номер шага, что он точно ошибся на одном из шагов \(1, 2, \ldots, t\).
Примечание
В первом примере Ильдар мог получить такой массив, не совершив ни одной ошибки. Вот как он мог это сделать:
- \(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\) — явно ошибка.