← 返回题目列表

AtCoder · abc271_c

F. 漫画

中文机器翻译题面 查看原题

分数: 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.