← 返回题目列表

Codeforces · 1054/B

B. 附加墨西哥

中文机器翻译题面 查看原题

最初 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 < i_2 < \ldots < i_k < m$$$ 的某个子集(可能为空),其中 $$$0 \leq k < m$$$,并将 $$$mex(a_{i_1}, a_{i_2}, \ldots a_{i_k})$$$ 添加到数组末尾。

执行完所有步骤后,Ildar 认为他可能在某个地方犯了错误。他要求你确定给定数组 $$$a_1, a_2, \ldots, a_n$$$ 的最小步骤 $$$t$$$,这样他肯定在步骤 $$$1, 2, \ldots, t$$$ 中的至少一个步骤上犯了错误,或者确定他可以毫无错误地获得这个数组。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — Ildar 迈出的步数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — Ildar 获得的数组。

输出

如果 Ildar 可以在每个步骤中选择子集,结果数组为 $$$a_1, a_2, \ldots, a_n$$$,则打印 $$$-1$$$。

否则打印单个整数 $$$t$$$ — 步骤的最小索引,使得步骤 $$$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

注意

在第一个示例中,Ildar 可能没有犯错误。这是他可以遵循的过程。

- $$$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$$$ 肯定是错误的。