题目描述

噜噜在追一部长达 $s$ 期的连载（每期从 $1,2,3,\dots$ 编号）。
他手里有 $n$ 张“期数贴纸”，贴纸上写着某一期的编号：$a_1,a_2,\ldots,a_n$（不一定连续，可能重复）。
噜噜想从第 1 期开始按顺序观看，中间不允许跳期。可惜手里贴纸并不齐全，好在活动规则允许他：

用手上任意 2 张贴纸，兑换一张自己还没看的任意一期的贴纸。

（兑换会消耗这两张贴纸，并得到一张新贴纸；新贴纸的期数由噜噜自行选择。）

请你计算：在最优策略下，噜噜最多能看到第几期？

说明：为了不受总期数 $s$ 限制，可认为 $s$ 很大（题目保证数据满足 $2n < s$）。

输入格式

第一行：一个正整数 $n$。

第二行：$n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个正整数，表示噜噜最多能看到的期数编号。

5
1 2 3 1 5

输出

8

解释
先看 $1,2,3$；缺 $4$，用两张贴纸（$1$ 和 $1$）兑换到 $4$；再看$5$；
随后用两张贴纸（$2$ 和$3$）兑换到 $6$；再用（$4$和$5$）兑到 $7$；再用（$6$和 $7$）兑到 $8$；
此时只剩一张$8$的贴纸，无法再兑换，答案为 $8$。

3
6 2 6

3

数据范围与说明

• $20\%$ 的数据：小例子恰好有前 $n$ 期，即贴纸为 $1\sim n$。
• $40\%$ 的数据：$1 \le n \le 1000$。
• $100\%$ 的数据：$1 \le n \le 10^6,a_i \le 2 \times n$（保证 $2n < s$）。