Codeforces Round #358 (Div. 2) -- B. Alyona and Mex （思路水题）

B. Alyona and Mex

time limit per test

memory limit per test

input

output

Someone gave Alyona an array containing n positive integers a₁, a₂, ..., a_n. In one operation, Alyona can choose any element of the array and decrease it, i.e. replace with any positive integer that is smaller than the current one. Alyona can repeat this operation as many times as she wants. In particular, she may not apply any operation to the array at all.

Formally, after applying some operations Alyona will get an array of n positive integers b₁, b₂, ..., b_n such that 1 ≤ b_i ≤ a_i for every 1 ≤ i ≤ n. Your task is to determine the maximum possible value of mex of this array.

Mex of an array in this problem is the minimum positive integer that doesn't appear in this array. For example, mex of the array containing 1, 3 and 4 is equal to 2, while mex of the array containing 2, 3 and 2 is equal to 1.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of elements in the Alyona's array.

The second line of the input contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) — the elements of the array.

Output

Print one positive integer — the maximum possible value of mex of the array after Alyona applies some (possibly none) operations.

Examples

Input

5 1 3 3 3 6

Output

5

Input

2 2 1

Output

3

Note

In the first sample case if one will decrease the second element value to 2 and the fifth element value to 4 then the mex value of resulting array 1 2 3 3 4 will be equal to 5.

To reach the answer to the second sample case one must not decrease any of the array elements.

大体题意：

给你n 个数，你可以任意交换两个数的位置，你也可以把一个数减小。问最后mex数最大是多少，mex数是这n个数中未出现数的最小值。

思路：

先给n个数排序，那么设mex = 1，发现一个数大于等于mex  mex++，最后输出即可！

为什么这样做可以呢？

因为要想让mex尽可能的大，你就尽量的向1，2，3，4这样连续子序列去凑，排好序后，比如说第二个数是1000吧，把它变成2后 那么mex就成了3，否则mex是2，依次类推……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 10;
int a[maxn];
int main(){
    int n;
    while(scanf("%d",&n) == 1){
        for (int i = 0; i < n; ++i){
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        int ans = 1;
        for (int i = 0; i < n; ++i){
            if (a[i] >= ans)++ans;
        }
        printf("%d\n",ans);

    }
    return 0;
}