问题描述

高桥打算阅读一部漫画系列《Snuke-kun》共计 $10^9$ 卷。
起初，高桥有 $N$ 本这个系列的书。第 $i$ 本书是第 $a_i$ 卷。

高桥可以在开始阅读之前（只有这时候）任意次数地重复以下操作：

• 如果他只有 $1$ 本或更少的书，则什么都不做；否则，他会卖掉他所拥有的两本书，并用任意一卷的书来买一本。

然后，高桥按顺序阅读第 $1$ 卷，第 $2$ 卷，第 $3$ 卷，$\ldots$。但是，当他没有下一卷可读时，他就停止阅读这个系列（无论其他卷他是否拥有）。

找出他可以阅读到的系列的最新卷。如果他无法阅读任何卷，则答案为 $0$。

约束条件

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

输入

输入以以下格式从标准输入中给出：

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

输出

打印出答案。

样例输入 1

6
1 2 4 6 7 271

样例输出 1

4

在开始阅读这个系列之前，他可以进行以下操作：“卖掉第 $7$ 卷和第 $271$ 卷的书，并用第 $3$ 卷的书来代替”。然后，他各自有一本第 $1$ 卷、第 $2$ 卷、第 $3$ 卷、第 $4$ 卷和第 $6$ 卷。
然后，如果他开始阅读这个系列，他会阅读第 $1$ 卷、第 $2$ 卷、第 $3$ 卷和第 $4$ 卷，然后尝试阅读第 $5$ 卷。然而，他没有第 $5$ 卷，所以他在这个时候停止阅读。
无论操作中的选择如何，他都无法阅读第 $5$ 卷，所以答案是 $4$。

样例输入 2

10
1 1 1 1 1 1 1 1 1 1

样例输出 2

5

高桥可能有多本相同卷数的书。
对于这个输入，如果他在开始阅读这个系列之前进行以下 $4$ 次操作，他可以阅读到最多第 $5$ 卷：

• 卖掉两本第 $1$ 卷的书，并用第 $2$ 卷的书来代替。
• 卖掉两本第 $1$ 卷的书，并用第 $3$ 卷的书来代替。
• 卖掉两本第 $1$ 卷的书，并用第 $4$ 卷的书来代替。
• 卖掉两本第 $1$ 卷的书，并用第 $5$ 卷的书来代替。

样例输入 3

1
5

样例输出 3

0

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