分数: 300 点
问题陈述
高桥打算在 读漫画系列“Snuke-kun” 10^9 卷。
最初,高桥有 N 本系列书籍。 的 i- 第本书是卷 a_i.
Takahashi 可以重复以下操作任意次数(可能为零) 仅在他开始阅读之前:
- 如果他有,则不执行任何操作 1 以下书籍;否则,卖掉他拥有的两本书并购买一本任意卷的书。
然后,高桥读了卷 1,卷 2,卷 3, \ldots,按顺序。 然而,当他没有下一卷的书可供阅读时,他就会停止阅读该系列(无论他还有其他几卷)。
找到他能读到的该系列的最新卷。 如果他看不懂,请回答 0.
约束
- 1 \leq N \leq 3 \times 10^5
- 1 \leq a_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N a_1 \ldots a_N
输出
打印答案。
示例输入 1
6 1 2 4 6 7 271
示例输出 1
4
在他开始阅读该系列之前,他可以执行以下操作:“出售卷册 7 和 271 并购买一本书 3 代替。” 然后,他每卷一本书 1, 2, 3, 4,和 6.
如果他随后开始阅读该系列,他会阅读卷 1, 2, 3,和 4,然后尝试读取卷 5。 然而,他没有,所以他此时停止阅读。
无论操作中如何选择,他都无法读取卷 5,所以答案是 4.
示例输入 2
10 1 1 1 1 1 1 1 1 1 1
示例输出 2
5
高桥可能有多本同一卷的书。
对于这个输入,如果他执行以下操作 4 在他开始阅读该系列之前进行操作,他最多可以阅读卷 5,这是最大值:
- 出售两本书 1 并购买一本书 2 代替。
- 出售两本书 1 并购买一本书 3 代替。
- 出售两本书 1 并购买一本书 4 代替。
- 出售两本书 1 并购买一本书 5 代替。
示例输入 3
1 5
示例输出 3
0
高桥无法阅读卷 1.