漫画

题目描述

高桥要读一部共 $10^9$ 卷的漫画系列「Snuke 君」。

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

在开始阅读之前,高桥可以任意多次(可能为 0 次)重复以下操作:

如果手头的书有 1 本或更少,则不进行任何操作;否则,卖掉手中的两本书,换购任意一卷的一本书。

之后,高桥按第 1 卷、第 2 卷、第 3 卷……的顺序阅读。但是,当没有要读的下一卷的书时,他就停止阅读(与手中其他卷的书无关)。

求高桥能读到的最新卷数。如果他一本都读不了,则答案为 0。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

6
1 2 4 6 7 271

4

在开始阅读之前,他可以执行以下操作:「卖掉第 $7$ 卷和第 $271$ 卷的书,换购第 $3$ 卷的书」。于是,他拥有第 $1$、$2$、$3$、$4$、$6$ 卷各一本。

如果此时开始阅读,他会读完第 $1$、$2$、$3$、$4$ 卷,然后试图读第 $5$ 卷。然而他没有第 $5$ 卷,所以到此为止。

无论操作如何选择,他都无法读到第 $5$ 卷,因此答案是 $4$。

10
1 1 1 1 1 1 1 1 1 1

5

高桥可以有多本同一卷的书。

对于这个输入,如果在开始阅读前执行以下 4 次操作,他可以读到第 $5$ 卷,这是最大值:

卖掉两本第 $1$ 卷的书,换购第 $2$ 卷的书。

卖掉两本第 $1$ 卷的书,换购第 $3$ 卷的书。

卖掉两本第 $1$ 卷的书,换购第 $4$ 卷的书。

卖掉两本第 $1$ 卷的书,换购第 $5$ 卷的书。

1
5

0

高桥无法读到第 $1$ 卷。

数据范围

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq a_i \leq 10^9$
• 输入中的所有值均为整数。