ユキさんは、子供会の催しでみんなで遊べるようにすごろくを作りました。このすごろくでは、環状にマスが並んでいて、それぞれのマスには1以上の整数が書いてあります。
プレイヤーは出発点としてどこかのマスを選んで自分の駒を置きます。そのマスに書いてある数だけ、時計回りに駒を進めます。止まったマスに書いてある数だけ、再び時計回りに駒を進めます。これを繰り返して、出発点に選んだマスの上で駒が止まったら「あがり」です。
実際には、マスの選び方によっては絶対に「あがり」にならない場合もあります。ユキさんは、このすごろくで「あがり」にたどり着けるマスの個数を数えようとしています。
すごろくの情報を入力とし、「あがり」にたどり着けるマスの個数を報告するプログラムを作成せよ。
入力は以下の形式で与えられる。
N a1 a2 ... aN
1行目にすごろくに含まれるすべてのマスの個数 N (1 ≤ N ≤ 100000) が与えられる。2行目に、それぞれのマスに書かれた数 ai (1 ≤ ai ≤ 109) が、時計回りに順番に与えられる。
「あがり」にたどり着けるマスの個数を1行に出力する。
3 1 1 1
3
3 1 1 2
2
8 2 3 7 3 3 3 4 4
6