問題文

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

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

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

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

制約

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

入力例 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