CF682B.Alyona and Mex

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Someone gave Alyona an array containing n positive integers _a_1, _a_2, ..., 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_1, _b_2, ..., 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.

有人给了阿廖娜一个包含 nn 个正整数 a1,a2,…,ana_1, a_2, \dots, a_n 的数组。在一次操作中,阿廖娜可以任选数组中的一个元素并将其减小,即用任意一个小于当前值的正整数来替换它。阿廖娜可以重复执行该操作任意多次。特别地,她也可以完全不进行任何操作。

形式上,在执行若干次操作后,阿廖娜将得到一个由 nn 个正整数 b1,b2,…,bnb_1, b_2, \dots, b_n 构成的数组,满足对每个 1≤i≤n1 \le i \le n,均有 1≤bi≤ai1 \le b_i \le a_i。你的任务是确定该数组可能达到的最大 mex 值。

本题中,一个数组的 mex(minimum excluded value)是指未出现在该数组中的最小正整数。例如,包含 1,31, 3 和 44 的数组的 mex 为 22;而包含 2,32, 3 和 22 的数组的 mex 为 11。

输入格式

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_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) — the elements of the array.

输入的第一行包含一个整数 nn(1 ≤ n ≤ 100 0001 ≤ n ≤ 100\,000)—— 表示 Alyona 数组中元素的个数。

输入的第二行包含 nn 个整数 a1, a2, ..., ana_1,\,a_2,\,...,\,a_n(1 ≤ ai ≤ 1091 ≤ a_i ≤ 10^9)—— 表示该数组的元素。

输出格式

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

输出一个正整数——Alyona 执行若干次(可能为零次)操作后,该数组的 mex 的最大可能值。

输入输出样例

  • 输入#1

    5
    1 3 3 3 6

    输出#1

    5
  • 输入#2

    2
    2 1

    输出#2

    3

说明/提示

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.

在第一个样例中,若将第二个元素的值减小为 2,第五个元素的值减小为 4,则所得数组 1 2 3 3 41\ 2\ 3\ 3\ 4 的 mex 值等于 55。

要得到第二个样例的答案,不能减小数组中的任何元素。

输入解题思路,AI测评打分。不知道怎么写?

首页