在这个问题中,某个数组的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