E. Replace with MEX
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Define $$$mex(b)$$$ as the minimum non-negative integer that doesn't appear in the array $$$b$$$. For example, $$$mex([1, 0, 2]) = 3$$$ and $$$mex([1]) = 0$$$.

Given an array $$$a$$$ of length $$$n$$$. You can do the following operation at most once:

  • Choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$), and let $$$m = mex(a[l \dots r])$$$ (where $$$a[l \dots r]$$$ is $$$a_l, a_{l + 1}, \dots a_r$$$).
  • For each $$$i$$$ ($$$l \le i \le r$$$), assign $$$a_i$$$ = $$$m$$$.

What is the maximum value of $$$mex(a)$$$ after performing the above operation at most once.

Input

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

The second line of the input consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$).

Output

Output a single integer — the maximum possible value of $$$mex(a)$$$.

Examples
Input
4
1 2 3 0
Output
4
Input
2
2 1
Output
2