Description

有一套正在连载的连环画。一开始，小爱只有其中的 <math xmlns="http://www.w3.org/1998/Math/MathML">n 本画册，它们在连环画中的序号分别为 <math xmlns="http://www.w3.org/1998/Math/MathML">a1,a2,…,an。这些画册不到整部漫画的一半，也就是说，连环画的画数是超过 <math xmlns="http://www.w3.org/1998/Math/MathML">2×n 的。

小爱需要从漫画的第一册开始看起，按照顺序一册册阅读。如果缺少了某本画册，小爱可以用手上任意两本连环画从二手市场上交换到任意一本画册。

例如，小爱有连环画的第一、二、四、五册，她可以先读前两册，然后用前两册交换到第三册，然后读第三到第五册，继续通过以旧换新的策略可以读到第七册。

给定 <math xmlns="http://www.w3.org/1998/Math/MathML">a1,a2,…,an，请计算小爱能看到第几册？

Input Format

• 第一行：单个整数 <math xmlns="http://www.w3.org/1998/Math/MathML">n
• 第二行：<math xmlns="http://www.w3.org/1998/Math/MathML">n 个整数 <math xmlns="http://www.w3.org/1998/Math/MathML">a1,a2,…,an
• 保证有 <math xmlns="http://www.w3.org/1998/Math/MathML">1≤a1≤a2≤⋯≤an≤2×n

Output Format

单个整数：表示答案

4
1 2 4 5

7

Hint

输入:
6
1 1 1 1 1 1
输出:
6

• 对于 <math xmlns="http://www.w3.org/1998/Math/MathML">30% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤n≤100
• 对于 <math xmlns="http://www.w3.org/1998/Math/MathML">60% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤n≤5000
• 对于 <math xmlns="http://www.w3.org/1998/Math/MathML">100% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤n≤1,000,000

Source

贪心 第四届上海市竞赛