0617 - 環状すごろく

時間制限 1 秒 / メモリ制限 256 MB / 得点 8 / Writer ei1417 / x 4 / 統計 /


TLE
1sec
MLE
256MB
得点
8

問題

ユキさんは、子供会の催しでみんなで遊べるようにすごろくを作りました。このすごろくでは、環状にマスが並んでいて、それぞれのマスには1以上の整数が書いてあります。

プレイヤーは出発点としてどこかのマスを選んで自分の駒を置きます。そのマスに書いてある数だけ、時計回りに駒を進めます。止まったマスに書いてある数だけ、再び時計回りに駒を進めます。これを繰り返して、出発点に選んだマスの上で駒が止まったら「あがり」です。

実際には、マスの選び方によっては絶対に「あがり」にならない場合もあります。ユキさんは、このすごろくで「あがり」にたどり着けるマスの個数を数えようとしています。

課題

すごろくの情報を入力とし、「あがり」にたどり着けるマスの個数を報告するプログラムを作成せよ。

入力

N
a1 a2 ... aN

1行目にすごろくに含まれるすべてのマスの個数N(1≦N≦100000)が与えられる。2行目に、それぞれのマスに書かれた数ai(1≦ai≦109)が、時計回りに順番に与えられる。

出力

「あがり」にたどり着けるマスの個数を1行に出力する。


入出力例

入力例1

3
1 1 1

出力例1

3

入力例2

3
1 1 2

出力例2

2

入力例3

8
2 3 7 3 3 3 4 4

出力例3

6