Nosaukums
Plaukšķi (plauks)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
88%

Definīcija

Mirko spēlē sekojošu spēli: Viņam ir kāršu kava, kas sastāv no N kārtīm, kas numurētas no 1 līdz N (kavā nav divu kāršu ar vienādiem numuriem). Kāršu kava tiek sajaukta.

Mirko sāk caurskatīt kavu, sākot ar virsējo kārti. Ņemot kārtis pēc kārtas, viņš meklē kārti ar numuru 1. Kad šī kārts ir atrasta, Mirko izņem to no kavas un līdzīgā veidā meklē kārtis ar numuru 2, 3, 4, utt., vienmēr sākot no tās vietas, kur tika atrasta iepriekšējā kārts. Katru reizi, kad visa kava ir caurskatīta, Mirko sasit plaukstas un atkal sāk kavas caurskati no sākuma.

Šīs darbības pamazām iztukšo kāršu kaudzīti līdz kamēr pēdējā kārts (ar numuru N) tiek izņemta un spēle beidzas.

Uzrakstiet programmu, kas dotai sākotnējai kāršu secībai kavā nosaka, cik reizes Mirko sasitīs plaukstas spēles laikā!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dota naturāla skaitļa N vērtība (1 ≤N≤100000). Katrā no nākošajām N faila rindām dots pa vienam naturālam skaitlim - kārtējās kārts numuram kavā pēc sākotnējās sajaukšanas.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada viens vesels skaitlis - plaukstu sasišanu skaits.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā


Paraugdati

Stdin
3
2
1
3
Stdout
1

Stdin
5
3
5
1
4
2
Stdout
2

Stdin
7
3
6
7
1
5
4
2
Stdout
3

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.