In this problem MEX of a certain array is the smallest positive integer not contained in this array.

Everyone knows this definition, including Lesha. But Lesha loves MEX, so he comes up with a new problem involving MEX every day, including today.

You are given an array $a$ of length $n$. Lesha considers all the non-empty subarrays of the initial array and computes MEX for each of them. Then Lesha computes MEX of the obtained numbers.

An array $b$ is a subarray of an array $a$, if $b$ can be obtained from $a$ by deletion of several (possible none or all) elements from the beginning and several (possibly none or all) elements from the end. In particular, an array is a subarray of itself.

Lesha understands that the problem is very interesting this time, but he doesn't know how to solve it. Help him and find the MEX of MEXes of all the subarrays!


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the array. 

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of the array.


-----Output-----

Print a single integer — the MEX of MEXes of all subarrays.


-----Examples-----
Input
3
1 3 2

Output
3

Input
5
1 4 3 1 2

Output
6

Difficulty: MEDIUM

Starter code:

Solutions:
import sys, math
import io, os
data = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
from itertools import permutations, combinations

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = float('inf')
mod = int(1000000000.0) + 7

class SegmentTree:

	def __init__(self, data, default=0, func=min):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		while idx:
			idx >>= 1
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])

	def __len__(self):
		return self._len

	def query(self, start, stop):
		start += self._size
		stop += self._size
		res_left = res_right = self._default
		while start < stop:
			if start & 1:
				res_left = self._func(res_left, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res_right = self._func(self.data[stop], res_right)
			start >>= 1
			stop >>= 1
		return self._func(res_left, res_right)

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
n = int(data())
a = mdata()
if len(set(a)) == 1 and 1 in a:
	out(1)
	exit()
S = SegmentTree(list(range(-n - 1, 0)), INF)
m = [0] * (n + 1)
for i in range(n):
	x = a[i]
	ind = S.query(0, x)
	if ind < 0:
		m[ind] = 1
	else:
		m[a[ind] - 1] = 1
	S.__setitem__(x - 1, i)
for i in range(n + 1):
	ind = S.query(0, i + 1)
	if ind < 0:
		m[ind] = 1
	else:
		m[a[ind] - 1] = 1
for i in range(n + 1):
	if m[i] == 0:
		out(i + 1)
		exit()
out(n + 2)


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for k in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** (-10)

class SegTree:

	def __init__(self, n, func, intv, A=[]):
		self.n = n
		self.func = func
		self.intv = intv
		n2 = 1
		while n2 < n:
			n2 <<= 1
		self.n2 = n2
		self.tree = [self.intv] * (n2 << 1)
		if A:
			for i in range(n):
				self.tree[n2 + i] = A[i]
			for i in range(n2 - 1, -1, -1):
				self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def update(self, i, x):
		i += self.n2
		self.tree[i] = x
		while i > 0:
			i >>= 1
			self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def add(self, i, x):
		self.update(i, self.get(i) + x)

	def query(self, a, b):
		l = a + self.n2
		r = b + self.n2
		s = self.intv
		while l < r:
			if r & 1:
				r -= 1
				s = self.func(s, self.tree[r])
			if l & 1:
				s = self.func(s, self.tree[l])
				l += 1
			l >>= 1
			r >>= 1
		return s

	def get(self, i):
		return self.tree[i + self.n2]

	def all(self):
		return self.tree[1]

	def print(self):
		for i in range(self.n):
			print(self.get(i), end=' ')
		print()
N = INT()
A = LIST()
seg = SegTree(N + 2, min, INF, [-1] * (N + 2))
mex = [0] * (N + 2)
if sorted(A, reverse=1)[0] != 1:
	mex[1] = 1
for i in range(N):
	if A[i] == 1:
		seg.update(A[i], i)
		continue
	prev = seg.get(A[i])
	l = 1
	r = A[i]
	mn = seg.query(l, r)
	if mn > prev:
		mex[A[i]] = 1
	seg.update(A[i], i)
for a in range(2, N + 2):
	prev = seg.get(a)
	l = 1
	r = a
	mn = seg.query(l, r)
	if mn > prev:
		mex[a] = 1
ans = N + 2
for i in range(1, N + 2):
	if not mex[i]:
		ans = i
		break
print(ans)


from typing import TypeVar, Generic, Callable, List
import sys
from array import array

def input():
	return sys.stdin.buffer.readline().decode('utf-8')
T = TypeVar('T')

class SegmentTree(Generic[T]):
	__slots__ = ['size', 'tree', 'identity', 'op', 'update_op']

	def __init__(self, size: int, identity: T, op: Callable[[T, T], T], update_op: Callable[[T, T], T]) -> None:
		self.size = size
		self.tree = [identity] * (size * 2)
		self.identity = identity
		self.op = op
		self.update_op = update_op

	def build(self, a: List[T]) -> None:
		tree = self.tree
		tree[self.size:self.size + len(a)] = a
		for i in range(self.size - 1, 0, -1):
			tree[i] = self.op(tree[i << 1], tree[(i << 1) + 1])

	def find(self, left: int, right: int) -> T:
		left += self.size
		right += self.size
		(tree, result, op) = (self.tree, self.identity, self.op)
		while left < right:
			if left & 1:
				result = op(tree[left], result)
				left += 1
			if right & 1:
				result = op(tree[right - 1], result)
			(left, right) = (left >> 1, right >> 1)
		return result

	def update(self, i: int, value: T) -> None:
		(op, tree) = (self.op, self.tree)
		i = self.size + i
		tree[i] = self.update_op(tree[i], value)
		while i > 1:
			i >>= 1
			tree[i] = op(tree[i << 1], tree[(i << 1) + 1])
n = int(input())
a = list(map(int, input().split()))
segt = SegmentTree[int](n + 10, 10 ** 9, min, max)
segt.build([-1] * (n + 10))
prev = [-1] * (n + 10)
flag = [0] + [1] * (n + 10)
for (i, x) in enumerate(a):
	if x != 1:
		flag[1] = 0
		left = segt.find(1, x)
		if left > prev[x]:
			flag[x] = 0
	prev[x] = i
	segt.update(x, i)
for (i, f) in enumerate(flag):
	if f and (not prev[i] < segt.find(1, i) < n):
		print(i)
		exit()


n = int(input())
a = list(map(int, input().split()))
ans = 1
(last, pre) = ([0] * (n + 2), [n + 2] * (n + 2))
b = [n + 1] * (n + 1)
for i in range(1, n + 1):
	pre[i] = last[a[i - 1]]
	last[a[i - 1]] = i

def update(i, x):
	while i <= n:
		b[i] = min(b[i], x)
		i += i & -i

def getmin(i):
	ans = n + 2
	while i:
		ans = min(ans, b[i])
		i -= i & -i
	return ans
vis = [False] * (n + 3)
for i in range(1, n + 1):
	update(i, last[i])
for i in range(1, n + 2):
	if last[i] != n and getmin(i - 1) > last[i]:
		vis[i] = True
for i in range(n, 0, -1):
	update(a[i - 1], pre[i])
	if pre[i] != i - 1 and getmin(a[i - 1] - 1) > pre[i]:
		vis[a[i - 1]] = True
ans = 1
while vis[ans]:
	ans += 1
print(ans)


class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.range = [(-1, n)] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
			self.range[self.num + i] = (i, i)
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
			self.range[i] = (self.range[2 * i][0], self.range[2 * i + 1][1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
n = int(input())
p = list(map(int, input().split()))
pos = [[] for i in range(n + 2)]
for i in range(n):
	pos[p[i]].append(i)
query = [[] for i in range(n)]
for i in range(1, n + 2):
	for j in range(len(pos[i]) - 1):
		L = pos[i][j] + 1
		R = pos[i][j + 1] - 1
		if L <= R:
			query[R].append((L, i))
	if pos[i]:
		if pos[i][0] != 0:
			query[pos[i][0] - 1].append((0, i))
		if pos[i][-1] != n - 1:
			query[n - 1].append((pos[i][-1] + 1, i))
	else:
		query[n - 1].append((0, i))
flag = [False for i in range(n + 3)]
init = [-1] * (n + 2)
init[0] = n
lastappeared = SegmentTree(init, min, -1)
for i in range(n):
	lastappeared.update(p[i], i)
	for (l, val) in query[i]:
		check = lastappeared.bisect_l(0, n + 2, l - 1)
		if check >= val or check == -1:
			flag[val] = True
for i in range(1, n + 3):
	if not flag[i]:
		print(i)
		break


n = int(input())
a = list(map(int, input().split()))
mn = [-1 for _ in range(n * 4)]

def Set(c, ss, se, qi, f):
	if ss == se:
		mn[c] = f
	else:
		mid = ss + se >> 1
		if qi <= mid:
			Set(c * 2, ss, mid, qi, f)
		else:
			Set(c * 2 + 1, mid + 1, se, qi, f)
		mn[c] = min(mn[c * 2], mn[c * 2 + 1])

def Walk(c, ss, se, k):
	if ss == se:
		return ss + 1 if mn[c] > k else ss
	mid = ss + se >> 1
	if mn[c * 2] > k:
		return Walk(c * 2 + 1, mid + 1, se, k)
	else:
		return Walk(c * 2, ss, mid, k)
las = [-1 for _ in range(n + 2)]
was = [False for _ in range(n + 3)]
for i in range(n):
	if las[a[i]] != i - 1:
		was[Walk(1, 1, n, las[a[i]])] = True
	las[a[i]] = i
	Set(1, 1, n, a[i], i)
for i in range(1, n + 2):
	if las[i] != n - 1:
		was[Walk(1, 1, n, las[i])] = True
ans = 1
while was[ans]:
	ans += 1
print(ans)


import collections
n = int(input())
a = list(map(int, input().split()))

def lowbit(x):
	return x & -x

def add(x, k):
	while x <= n:
		tree[x] = max(tree[x], k)
		x += lowbit(x)

def query(x):
	ans = 0
	while x > 0:
		ans = max(ans, tree[x])
		x -= lowbit(x)
	return ans
G = collections.defaultdict(list)
tree = collections.defaultdict(int)
for i in range(1, n + 2):
	G[i].append(0)
for i in range(1, n + 1):
	G[a[i - 1]].append(i)
for i in range(1, n + 2):
	G[i].append(n + 1)
ans = 1
for i in range(1, n + 2):
	(flag, sz) = (0, len(G[i]))
	if sz == n + 2:
		ans = i
		break
	for j in range(1, sz):
		f = query(G[i][j - 1] + 1)
		if f < G[i][j]:
			flag = 1
	if not flag:
		break
	for j in range(1, sz):
		f = G[i][j - 1] + 1
		add(f, G[i][j])
	ans = i + 1
print(ans)


from math import inf, log2

class SegmentTree:

	def __init__(self, array, func=max):
		self.n = len(array)
		self.size = 2 ** (int(log2(self.n - 1)) + 1) if self.n != 1 else 1
		self.func = func
		self.default = 0 if self.func != min else inf
		self.data = [self.default] * (2 * self.size)
		self.process(array)

	def process(self, array):
		self.data[self.size:self.size + self.n] = array
		for i in range(self.size - 1, -1, -1):
			self.data[i] = self.func(self.data[2 * i], self.data[2 * i + 1])

	def query(self, alpha, omega):
		if alpha == omega:
			return self.data[alpha + self.size]
		res = self.default
		alpha += self.size
		omega += self.size + 1
		while alpha < omega:
			if alpha & 1:
				res = self.func(res, self.data[alpha])
				alpha += 1
			if omega & 1:
				omega -= 1
				res = self.func(res, self.data[omega])
			alpha >>= 1
			omega >>= 1
		return res

	def update(self, index, value):
		index += self.size
		self.data[index] = value
		index >>= 1
		while index:
			self.data[index] = self.func(self.data[2 * index], self.data[2 * index + 1])
			index >>= 1
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	n = int(input())
	a = list(map(int, input().split()))
	if a == [1] * n:
		print(1)
		quit()
	di = {}
	for i in range(n):
		if a[i] not in di:
			di[a[i]] = [-1]
		di[a[i]] += [i]
	queries = []
	dx = [0] * (n + 69)
	for each in di:
		di[each] += [n]
		for j in range(len(di[each]) - 1):
			if di[each][j] + 1 == n or di[each][j + 1] - 1 == -1:
				continue
			queries += [[di[each][j] + 1, di[each][j + 1] - 1, each]]
	queries += [[0, n - 1, n + 3]]
	queries = sorted(queries, key=lambda x: x[1])
	st = SegmentTree([69696969] + [-1] * (n + 69), func=min)
	j = 0
	for i in range(n):
		st.update(a[i], i)
		while j < len(queries) and queries[j][1] == i:
			less_than = queries[j][0]
			(alpha, omega) = (0, n + 1)
			while alpha < omega:
				mid = (alpha + omega) // 2
				if st.query(alpha, mid) < less_than:
					omega = mid
				else:
					alpha = mid + 1
			dx[queries[j][2]] = max(dx[queries[j][2]], omega)
			j += 1
	ans = 0
	for i in range(1, n + 2):
		if dx[i] != i:
			ans = i
			break
	if dx[n + 3] == ans:
		ans += 1
	print(ans)