Appending Mex

题意翻译

### 题目描述 一开始有一个空的序列，每一次可以选取这个序列的一个子序列，并将这个子序列的 $\text{mex}$ 值加入到序列的尾部。 给定长度为 $n$ 的序列 $a_i$，求最小的 $t$ 使得无法通过若干次操作得到序列 $a_1,\ldots,a_t$。 ### 输入格式 第一行一个正整数 $n$。 第二行 $n$ 个正整数，第 $i$ 个表示 $a_i$。 ### 输出格式 如果可以通过若干次操作得到整个序列输出 $-1$，否则输出最小的 $t$ 使得若干次操作后无法得到 $a_1,\ldots,a_t$。 Translated By Karry5307

题目描述

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 $ .

输入输出样例

输入样例 #1

4
0 1 2 1

输出样例 #1

-1

输入样例 #2

3
1 0 1

输出样例 #2

1

输入样例 #3

4
0 1 2 239

输出样例 #3

4

说明

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.