102712: [AtCoder]ABC271 C - Manga

Problem Statement

Takahashi is going to read a manga series "Snuke-kun" in $10^9$ volumes.
Initially, Takahashi has $N$ books of this series. The $i$-th book is Volume $a_i$.

Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:

• Do nothing if he has $1$ or less books; otherwise, sell two of the books he has and buy one book of any volume instead.

Then, Takahashi reads Volume $1$, Volume $2$, Volume $3$, $\ldots$, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).

Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be $0$.

Constraints

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq a_i \leq 10^9$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$
$a_1$ $\ldots$ $a_N$

Output

Print the answer.

Sample Input 1

6
1 2 4 6 7 271

Sample Output 1

4

Before he begins to read the series, he may do the following operation: "sell books of Volumes $7$ and $271$ and buy one book of Volume $3$ instead." Then, he has one book each of Volumes $1$, $2$, $3$, $4$, and $6$.
If he then begins to read the series, he reads Volumes $1$, $2$, $3$, and $4$, then tries to read Volume $5$. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume $5$, so the answer is $4$.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

5

Takahashi may have multiple books of the same volume.
For this input, if he performs the following $4$ operations before he begins to read the series, he can read up to Volume $5$, which is the maximum:

• Sell two books of Volume $1$ and buy a book of Volume $2$ instead.
• Sell two books of Volume $1$ and buy a book of Volume $3$ instead.
• Sell two books of Volume $1$ and buy a book of Volume $4$ instead.
• Sell two books of Volume $1$ and buy a book of Volume $5$ instead.

Sample Input 3

1
5

Sample Output 3

0

Takahashi cannot read Volume $1$.

问题描述

高桥打算阅读一部名为“Snuke-kun”的漫画系列，共有$10^9$卷。

最初，高桥有$N$本这个系列的书。第$i$本书是第$a_i$卷。

高桥可以在开始阅读之前重复执行任意多次（包括零次）以下操作：

• 如果他拥有的书少于或等于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卷。