C - Manga 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

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

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

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

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

高橋君が『すぬけ君』を最大で何巻まで読めるかを求めてください。ただし、1 巻を読めない場合の答えは 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 冊買う」という内容で操作をすると、高橋君は 1 巻、2 巻、3 巻、4 巻、6 巻を 1 冊ずつ持っている状態になります。
この状態から『すぬけ君』を読み始めると、高橋君は 1 巻、2 巻、3 巻、4 巻を読み、続いて 5 巻を読もうとしますが持っていないためこの時点で『すぬけ君』を読むのをやめます。
操作の方法を変えても 5 巻を読むことは出来ないため、4 が答えです。

入力例 2

10
1 1 1 1 1 1 1 1 1 1

出力例 2

5

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

  • 1 巻を 2 冊選んで売り、代わりに 2 巻を選んで 1 冊買う
  • 1 巻を 2 冊選んで売り、代わりに 3 巻を選んで 1 冊買う
  • 1 巻を 2 冊選んで売り、代わりに 4 巻を選んで 1 冊買う
  • 1 巻を 2 冊選んで売り、代わりに 5 巻を選んで 1 冊買う

入力例 3

1
5

出力例 3

0

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

Score : 300 points

Problem Statement

Takahashi is going to read a manga series "Snuke-kun" in 10^9 volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume a_i.

Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:

  • Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.

Then, Takahashi reads Volume 1, Volume 2, Volume 3, \ldots, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).

Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be 0.

Constraints

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq a_i \leq 10^9
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
a_1 \ldots a_N

Output

Print the answer.

Sample Input 1

6
1 2 4 6 7 271

Sample Output 1

4

Before he begins to read the series, he may do the following operation: "sell books of Volumes 7 and 271 and buy one book of Volume 3 instead." Then, he has one book each of Volumes 1, 2, 3, 4, and 6.
If he then begins to read the series, he reads Volumes 1, 2, 3, and 4, then tries to read Volume 5. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume 5, so the answer is 4.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

5

Takahashi may have multiple books of the same volume.
For this input, if he performs the following 4 operations before he begins to read the series, he can read up to Volume 5, which is the maximum:

  • Sell two books of Volume 1 and buy a book of Volume 2 instead.
  • Sell two books of Volume 1 and buy a book of Volume 3 instead.
  • Sell two books of Volume 1 and buy a book of Volume 4 instead.
  • Sell two books of Volume 1 and buy a book of Volume 5 instead.

Sample Input 3

1
5

Sample Output 3

0

Takahashi cannot read Volume 1.