Maximize MEX

Time limit1sMemory limit1024 MB

Summary

Given a multiset of N integers below N, repeatedly replace any chosen subset with its mex until one element remains. Find the largest possible final value.

Level: Medium7 of 10
Topics: Greedy, Math
Solved: No attempts yet

Statement

A multiset $S$ of integers is given.

Initially, $S$ consists of $N$ elements $a_1,a_2,\cdots,a_N$ .

Repeat the following operation as many times as you want until $S$ has exactly one element.

Choose a non-empty subset $T$ of $S$ . Remove $T$ from $S$ , then insert into $S$ the smallest non-negative integer that does not appear in $T$ .

After performing the operations appropriately, find the maximum possible value of the single element left in $S$ .

Input

The first line contains an integer $N$ . $(2\leq N \leq 300\,000)$

The second line contains the sequence $a_1,a_2,\cdots,a_N$ of integers, separated by spaces. $(0\leq a_i < N)$

Output

Print the maximum possible value of the element remaining in $S$ when the operations are performed appropriately.

Examples4

Example 1
Input
```
3
0 1 2
```
Expected output
```
3
```
Example 2
Input
```
4
3 3 3 3
```
Expected output
```
3
```
Example 3
Input
```
5
0 0 3 2 3
```
Expected output
```
4
```
Example 4
Input
```
2
0 0
```
Expected output
```
2
```