B - リス

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

キリギリスとスローロリスがクリスマスケーキを買うために行列に並びました。

それを見ていたツーリストさんによると以下の情報が分かっています。

  • 合計 N 匹の動物が順番に行列に並んだ。
  • 行列に並んだ動物は全てキリギリスかスローロリスのどちらかである。
  • i 番目に来て行列に並んだ動物はちょうど A_i 匹の動物を順番抜かしした。
  • スローロリスがスローロリスを抜かしたことはなかった。

さて、スローロリスは最大で何匹行列に並んでいるでしょうか?

制約

  • 1≦N≦300,000
  • 0≦A_i≦i-1

入力

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

N
A_1 A_2 ... A_N

出力

行列に並んでいるスローロリスの匹数として考えられる最大値を出力せよ。


入力例 1

3
0 0 1

出力例 1

2

この入力では 3 番目の動物だけが順番抜かしをして、2 番目に来た動物を抜かしました。 そのため、2 番目の動物と 3 番目の動物がスローロリスだということはありえず、スローロリスは 2 匹以下しかいないことが分かります。

また、1 番目の動物と 2 番目の動物がスローロリスだったということはありうるため、答えは 2 匹となります。


入力例 2

4
0 1 2 3

出力例 2

1

この入力では、2 匹以上のスローロリスがいたということはありえません。


入力例 3

7
0 0 1 0 0 2 4

出力例 3

4