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

输入 #1

6
1 2 4 6 7 271

输出 #1

4

输入输出样例 #2

输入 #2

10
1 1 1 1 1 1 1 1 1 1

输出 #2

5

输入输出样例 #3

输入 #3

1
5

输出 #3

0

说明/提示

限制条件

• $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 翻译