AT_abc271_c [ABC271C] Manga

[problemUrl]: https://atcoder.jp/contests/abc271/tasks/abc271_c 高橋君は全 $ 10^9 $ 巻の漫画『すぬけ君』を読むことにしました。 初め、高橋君は『すぬけ君』の単行本を $ N $ 冊持っています。$ i $ 番目の単行本は $ a_i $ 巻です。 高橋君は『すぬけ君』を**読み始める前に限り**次の操作を $ 0 $ 回以上何度でも繰り返せます。 - 現在持っている単行本が $ 1 $ 冊以下の場合、何もしない。そうでない場合、現在持っている単行本から $ 2 $ 冊を選んで売り、代わりに好きな巻を選んで $ 1 $ 冊買う その後、高橋君は『すぬけ君』を $ 1 $ 巻、$ 2 $ 巻、$ 3 $ 巻、$ \ldots $ と順番に読みます。ただし、次に読むべき巻を持っていない状態になった場合、(他の巻を持っているかどうかに関わらず)その時点で『すぬけ君』を読むのをやめます。 高橋君が『すぬけ君』を最大で何巻まで読めるかを求めてください。ただし、$ 1 $ 巻を読めない場合の答えは $ 0 $ とします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ \ldots $ $ a_N $

答えを出力せよ。

### 制約 - $ 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 $ 巻を読めません。