問題文

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

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

• 合計 $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