← 返回题目列表

Codeforces · 1436/E

E. 复杂的计算

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

在这个问题中,某个数组的MEX是该数组中不包含的最小正整数。

每个人都知道这个定义,包括 Lesha。但Lesha很喜欢MEX,所以他每天都会提出一个涉及MEX的新问题,包括今天。

给你一个长度为 $$$n$$$ 的数组 $$$a$$$。 Lesha 考虑初始数组的所有非空子数组并为每个子数组计算 MEX。然后 Lesha 计算获得的数字的 MEX。

数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过删除开头的几个(可能没有或全部)元素和末尾的几个(可能没有或全部)元素从 $$$a$$$ 获得。特别是,数组是其自身的子数组。

Lesha明白这次的问题很有趣,但他不知道如何解决。帮助他找到所有子数组的 MEX 中的 MEX!

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组的长度。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组的元素。

输出

打印单个整数 — 所有子数组的 MEX 的 MEX。

示例

输入 #1

3
1 3 2

输出 #1

3

输入 #2

5
1 4 3 1 2

输出 #2

6