B - リス
解説
/
実行時間制限: 2 sec / メモリ制限: 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