Score : $300$ points

问题描述

Takahashi 打算阅读一部共 $10^9$ 卷的漫画系列 "Snuke-kun"。
最初，Takahashi 已拥有该系列的 $N$ 本书。其中第 $i$ 本书是第 $a_i$ 卷。

在 开始阅读之前，Takahashi 可以任意次数（包括零次）进行以下操作：

• 如果他拥有 1 本或更少的书，则不做任何操作；否则，卖出他所拥有的两本书，并用任意一卷的书替换。

然后，Takahashi 按顺序阅读第 1 卷、第 2 卷、第 3 卷、……。但是，当他没有下一本需要阅读的卷时，他会停止阅读该系列（不论他还拥有其他哪些卷的书）。

找出他能够读到的最晚卷数。如果他无法阅读任何卷，则答案为 $0$。

以上为通义千问 qwen-max 翻译，仅供参考。

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$.

update @ 2024/3/10 11:25:24