题目描述

高橋君は全 $10^9$ 巻の漫画『すぬけ君』を読むことにしました。
初め、高橋君は『すぬけ君』の単行本を $N$ 冊持っています。$i$ 番目の単行本は $a_i$ 巻です。

高橋君は『すぬけ君』を読み始める前に限り次の操作を $0$ 回以上何度でも繰り返せます。

• 現在持っている単行本が $1$ 冊以下の場合、何もしない。そうでない場合、現在持っている単行本から $2$ 冊を選んで売り、代わりに好きな巻を選んで $1$ 冊買う

その後、高橋君は『すぬけ君』を $1$ 巻、$2$ 巻、$3$ 巻、$\ldots$ と順番に読みます。ただし、次に読むべき巻を持っていない状態になった場合、(他の巻を持っているかどうかに関わらず)その時点で『すぬけ君』を読むのをやめます。

高橋君が『すぬけ君』を最大で何巻まで読めるかを求めてください。ただし、$1$ 巻を読めない場合の答えは $0$ とします。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

高桥现在有 $n$ 本书 $a_1,a_2,a_3,...,a_n$。

这 $n$ 本书属于同一个连载漫画，高桥希望他能在开始看前，从第一册开始，尽可能多的准备不间断的 $k$ 册（如果有第一册和第三册但没有第二册是不行的）。

高桥可以将两本书卖掉，买一本新书书（这一本新书可以是任意册），问 $k$ 最多是多少。

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$
• 入力はすべて整数

Sample Explanation 1

『すぬけ君』を読み始める前に「$7$ 巻と $271$ 巻を選んで売り、代わりに $3$ 巻を選んで $1$ 冊買う」という内容で操作をすると、高橋君は $1$ 巻、$2$ 巻、$3$ 巻、$4$ 巻、$6$ 巻を $1$ 冊ずつ持っている状態になります。 この状態から『すぬけ君』を読み始めると、高橋君は $1$ 巻、$2$ 巻、$3$ 巻、$4$ 巻を読み、続いて $5$ 巻を読もうとしますが持っていないためこの時点で『すぬけ君』を読むのをやめます。 操作の方法を変えても $5$ 巻を読むことは出来ないため、$4$ が答えです。

Sample Explanation 2

高橋君は同じ巻を $2$ 冊以上持っているかもしれません。 この入力に対しては以下のように $4$ 回操作をしてから『すぬけ君』を読み始めることで $5$ 巻まで読むことが出来、これが最大です。 - $1$ 巻を $2$ 冊選んで売り、代わりに $2$ 巻を選んで $1$ 冊買う - $1$ 巻を $2$ 冊選んで売り、代わりに $3$ 巻を選んで $1$ 冊買う - $1$ 巻を $2$ 冊選んで売り、代わりに $4$ 巻を選んで $1$ 冊買う - $1$ 巻を $2$ 冊選んで売り、代わりに $5$ 巻を選んで $1$ 冊買う

Sample Explanation 3

高橋君は $1$ 巻を読めません。