AT_abc271_c [ABC271C] Manga

高桥君决定阅读全 $10^9$ 卷的漫画《すぬけ君》。 一开始，高桥君拥有 $N$ 本《すぬけ君》的单行本。第 $i$ 本单行本是第 $a_i$ 卷。 在**开始阅读《すぬけ君》之前**，高桥君可以进行如下操作，次数不限（可以为 $0$ 次）： - 如果当前持有的单行本数量不超过 $1$ 本，则不能进行任何操作。否则，可以从当前持有的单行本中选择任意 $2$ 本卖掉，然后任选一卷，买入该卷的 $1$ 本。 之后，高桥君会按顺序阅读《すぬけ君》的第 $1$ 卷、第 $2$ 卷、第 $3$ 卷、$\ldots$。如果在某一时刻没有下一卷可读（无论是否还持有其他卷），他就会停止阅读。 请你求出高桥君最多能连续读到第几卷《すぬけ君》。如果连第 $1$ 卷都无法阅读，答案为 $0$。

输入以如下格式从标准输入给出。 > $N$ $a_1$ $a_2$ $\ldots$ $a_N$

请输出答案。

## 限制条件 - $1 \leq N \leq 3 \times 10^5$ - $1 \leq a_i \leq 10^9$ - 所有输入均为整数。 ## 样例解释 1 在开始阅读《すぬけ君》之前，进行一次操作：“选择第 $7$ 卷和第 $271$ 卷卖掉，换购第 $3$ 卷”，此时高桥君拥有第 $1$ 卷、第 $2$ 卷、第 $3$ 卷、第 $4$ 卷和第 $6$ 卷各一本。接下来开始阅读时，高桥君可以依次读第 $1$ 卷、第 $2$ 卷、第 $3$ 卷、第 $4$ 卷，但当他想读第 $5$ 卷时却没有持有，因此在此时停止阅读。无论如何操作，都无法读到第 $5$ 卷，因此答案为 $4$。 ## 样例解释 2 高桥君可能会持有同一卷的多本。对于本输入，可以通过如下 $4$ 次操作，在开始阅读前使得最多能读到第 $5$ 卷： - 选择两本第 $1$ 卷卖掉，换购一本第 $2$ 卷 - 选择两本第 $1$ 卷卖掉，换购一本第 $3$ 卷 - 选择两本第 $1$ 卷卖掉，换购一本第 $4$ 卷 - 选择两本第 $1$ 卷卖掉，换购一本第 $5$ 卷 ## 样例解释 3 高桥君无法阅读第 $1$ 卷。 由 ChatGPT 4.1 翻译