4188: Manga

# Manga ### 内存 1024MB ### 时间 4S ## 题目描述 小A决定要读全套共$10^9$卷的漫画《鼠之助君》。开始时，小A有$N$本这个系列的单行本。第$i$本单行本是第$a_i$卷。 在开始阅读之前，小A可以重复执行以下操作任意次数（包括零次）： 如果当前只有$1$本或更少的单行本，则不执行任何操作；否则，从他拥有的单行本中选两本卖掉，并购买任意一卷的新单行本。 然后，小A会按顺序阅读第$1$卷、第$2$卷、第$3$卷……，依此类推。然而，当他没有下一卷要读的单行本时，无论他手上还有哪些其他卷数的单行本，他都会停止阅读这个系列。 请找出他能读到的最后一卷是哪一卷。如果他一卷也读不了，则答案为$0$。 ## 输入格式 输入数据由标准输入按以下格式提供： $N$ $a_1\ a_2\ ...\ a_N$ ## 输出格式 输出答案。 ## 输入输出样例 ### 输入样例1 ``` 6 1 2 4 6 7 271 ``` ### 输出样例1 ``` 4 ``` ### 输入样例2 ``` 10 1 1 1 1 1 1 1 1 1 1 ``` ### 输出样例2 ``` 5 ``` ### 输入样例3 ``` 1 5 ``` ### 输出样例3 ``` 0 ``` ## 数据范围与提示 【样例1说明】 在他开始阅读系列之前，他可以进行以下操作：“卖掉第$7$卷和第$271$卷的单行本，并购买一本第$3$卷的单行本代替。”然后，他将拥有第$1$卷、第$2$卷、第$3$卷、第$4$卷和第$6$卷各一本。 如果他此时开始阅读系列，他会阅读第$1$卷、第$2$卷、第$3$卷和第$4$卷，然后尝试阅读第$5$卷。但是，因为他没有第$5$卷，所以他会在这个时候停止阅读。 无论如何选择操作，他都无法阅读第$5$卷，所以答案是$4$。 【样例2说明】 小A可能有多本相同卷数的单行本。 对于这个输入，如果他在开始阅读系列之前进行以下$4$次操作，他可以读到第$5$卷，这是最大可能： - 卖掉两本第$1$卷，然后买一本第$2$卷。 - 卖掉两本第$1$卷，然后买一本第$3$卷。 - 卖掉两本第$1$卷，然后买一本第$4$卷。 - 卖掉两本第$1$卷，然后买一本第$5$卷。 【样例3说明】 小A不能读第1卷。 【数据范围】 - $1 ≤ N ≤ 3 × 10^5$ - $1 ≤ a_i ≤ 10^9$ - 所有输入数据都是整数。 ## 题目来源 ABC271C