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 \lt i_2 \lt \ldots \lt i_k \lt m$ (possibly, empty), where $0 \leq k \lt 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.

最初，Ildar 有一个空数组。他执行 $n$ 步操作。在每一步中，他选取当前数组中已添加的整数的一个子集，并将该子集的 mex（最小未出现非负整数）追加到数组末尾。

一个整数多重集的 mex 是该多重集中未出现的最小非负整数。例如，多重集 $[0, 2, 3]$ 的 mex 是 $1$，而多重集 $[1, 2, 1]$ 的 mex 是 $0$。

更形式化地，在第 $m$ 步（此时 Ildar 已拥有数组 $a_1, a_2, \ldots, a_{m-1}$），他选择某个下标子集 $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \lt m$（可能为空，即 $k = 0$，其中 $0 \leq k \lt m$），并把 $\mathrm{mex}(a_{i_1}, a_{i_2}, \ldots, a_{i_k})$ 追加到数组末尾。

在执行完所有步骤后，Ildar 认为他可能在某处出错了。他请你判断：对于给定的数组 $a_1, a_2, \ldots, a_n$，是否存在某个最小的步骤编号 $t$，使得他在步骤 $1, 2, \ldots, t$ 中必然至少犯了一个错误；若不存在这样的 $t$，则说明该数组可以完全无误地被构造出来。

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.

第一行包含一个整数 $n$（$1 \leq n \leq 100\,000$）—— 表示 Ildar 所做的步数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$）—— 表示 Ildar 得到的数组。

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

如果伊尔达尔能够在每一步中选择合适的子集，使得最终得到的数组为 $a_1, a_2, \ldots, a_n$，则输出 $-1$。

否则，输出一个整数 $t$ —— 满足在步骤 $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.

在第一个例子中，Ildar 可能完全没有出错。以下是其可能遵循的过程：

• 第 $1$ 步：初始数组为空。他可以选择空子集并得到 $0$，因为空集的 mex 为 $0$。将该值追加到末尾后，得到数组 $[0]$。
• 第 $2$ 步：当前数组为 $[0]$。他可以选择子集 $[0]$ 并得到整数 $1$，因为 $\mathrm{mex}(0) = 1$。将该值追加到末尾后，得到数组 $[0,1]$。
• 第 $3$ 步：当前数组为 $[0,1]$。他可以选择子集 $[0,1]$ 并得到整数 $2$，因为 $\mathrm{mex}(0,1) = 2$。将该值追加到末尾后，得到数组 $[0,1,2]$。
• 第 $4$ 步：当前数组为 $[0,1,2]$。他可以选择子集 $[0]$ 并得到整数 $1$，因为 $\mathrm{mex}(0) = 1$。将该值追加到末尾后，得到数组 $[0,1,2,1]$。

因此，他可以在不出错的情况下得到该数组，故答案为 $-1$。

在第二个例子中，他在第一步就一定出错了，因为他不可能得到除 $0$ 以外的任何其他值。

在第三个例子中，他可能在不出错的情况下得到 $[0, 1, 2]$，但 $239$ 显然错误。