CF1054B Appending Mex

Initially Ildar has an empty array. He performs $ n $ steps. On each step he takes a subset of integers already added to the array and appends the mex of this subset to the array. The mex of an multiset of integers is the smallest non-negative integer not presented in the multiset. For example, the mex of the multiset $ [0, 2, 3] $ is $ 1 $ , while the mex of the multiset $ [1, 2, 1] $ is $ 0 $ . More formally, on the step $ m $ , when Ildar already has an array $ a_1, a_2, \ldots, a_{m-1} $ , he chooses some subset of indices $ 1 \leq i_1 < i_2 < \ldots < i_k < m $ (possibly, empty), where $ 0 \leq k < m $ , and appends the $ mex(a_{i_1}, a_{i_2}, \ldots a_{i_k}) $ to the end of the array. After performing all the steps Ildar thinks that he might have made a mistake somewhere. He asks you to determine for a given array $ a_1, a_2, \ldots, a_n $ the minimum step $ t $ such that he has definitely made a mistake on at least one of the steps $ 1, 2, \ldots, t $ , or determine that he could have obtained this array without mistakes.

The first line contains a single integer $ n $ ( $ 1 \leq n \leq 100\,000 $ ) — the number of steps Ildar made. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i \leq 10^9 $ ) — the array Ildar obtained.

If Ildar could have chosen the subsets on each step in such a way that the resulting array is $ a_1, a_2, \ldots, a_n $ , print $ -1 $ . Otherwise print a single integer $ t $ — the smallest index of a step such that a mistake was made on at least one step among steps $ 1, 2, \ldots, t $ .

In the first example it is possible that Ildar made no mistakes. Here is the process he could have followed. - $ 1 $ -st step. The initial array is empty. He can choose an empty subset and obtain $ 0 $ , because the mex of an empty set is $ 0 $ . Appending this value to the end he gets the array $ [0] $ . - $ 2 $ -nd step. The current array is $ [0] $ . He can choose a subset $ [0] $ and obtain an integer $ 1 $ , because $ mex(0) = 1 $ . Appending this value to the end he gets the array $ [0,1] $ . - $ 3 $ -rd step. The current array is $ [0,1] $ . He can choose a subset $ [0,1] $ and obtain an integer $ 2 $ , because $ mex(0,1) = 2 $ . Appending this value to the end he gets the array $ [0,1,2] $ . - $ 4 $ -th step. The current array is $ [0,1,2] $ . He can choose a subset $ [0] $ and obtain an integer $ 1 $ , because $ mex(0) = 1 $ . Appending this value to the end he gets the array $ [0,1,2,1] $ . Thus, he can get the array without mistakes, so the answer is $ -1 $ . In the second example he has definitely made a mistake on the very first step, because he could not have obtained anything different from $ 0 $ . In the third example he could have obtained $ [0, 1, 2] $ without mistakes, but $ 239 $ is definitely wrong.