Manga

题目描述

Takahashi 将要阅读一套共有 $10^9$ 卷的漫画系列 “Snuke-kun”。
最初，Takahashi 拥有该系列的 $N$ 本书。第 $i$ 本是第 $a_i$ 卷。
Takahashi 可以在他开始阅读之前任意（包括零次）重复以下操作：

如果他拥有 $1$ 本或更少的书则什么也不做；否则，卖掉他拥有的两本书并换成任意一卷的一本书。

然后，Takahashi 按顺序阅读第 $1$ 卷、第 $2$ 卷、第 $3$ 卷、$\ldots$。然而，当他没有下一卷可读时，他就停止阅读（不论他还拥有其他哪些卷）。
求他最多能读到的最后一卷。如果他一本都读不到，答案为 $0$。

输入格式

输入按下述格式从标准输入给出： $N$ $a_1$ $\ldots$ $a_N$

输出格式

输出答案。

6
1 2 4 6 7 271

4

10
1 1 1 1 1 1 1 1 1 1

5

1
5

0

提示

$1 \leq N \leq 3 \times 10^5$ $1 \leq a_i \leq 10^9$ 输入中的所有数值均为整数。在他开始阅读系列之前，他可以进行如下操作：“卖掉第 $7$ 卷和第 $271$ 卷的书，换成一本第 $3$ 卷的书。” 然后，他拥有第 $1$、$2$、$3$、$4$、$6$ 卷各一本。
如果他随后开始阅读系列，他会阅读第 $1$、$2$、$3$、$4$ 卷，然后尝试阅读第 $5$ 卷。然而，他没有第 $5$ 卷，所以在此停下。
无论在操作中如何选择，他都无法读到第 $5$ 卷，所以答案是 $4$。
Takahashi 可能拥有多本相同卷数的书。
对于该输入，如果他在开始阅读系列之前执行以下 $4$ 次操作，他可以读到第 $5$ 卷，这是最大的可能：

卖掉两本第 $1$ 卷并换成一本第 $2$ 卷。 卖掉两本第 $1$ 卷并换成一本第 $3$ 卷。 卖掉两本第 $1$ 卷并换成一本第 $4$ 卷。 卖掉两本第 $1$ 卷并换成一本第 $5$ 卷。
Takahashi 无法读到第 $1$ 卷。

标签: AtCoder|abc271C

来源

AtCoder|abc271C