- Time limit: 1.00 s
- Memory limit: 512 MB
Jonossa on n lasta, jotka haluavat saada karkkia. Jokaisella vuorolla ensimmäisenä oleva lapsi saa karkin ja siirtyy sitten jonon perään.
Kuitenkin jonossa esiintyy etuilua: jokaisesta lapsesta tiedetään, että hän etuilee aina tietyn määrän jonon viimeisiä lapsia siirtyessään jonon perään.
Tehtäväsi on laskea, moniko lapsista ei saa ikinä karkkia, vaikka jonottaminen jatkuisi äärettömän kauan.
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku n.
Seuraavalla rivillä on n kokonaislukua c_1,c_2,\ldots,c_n: montako lasta kukin lapsi etuilee siirtyessään jonon perään.
Jono on esitetty niin, että vasemmanpuoleisin lapsi on ensimmäisenä ja oikeanpuoleisin lapsi on viimeisenä.
Tuloste
Tulosta yksi kokonaisluku: moniko lapsista ei saa ikinä karkkia.
Rajat
- 1 \le n \le 5 \cdot 10^5
- 0 \le c_i \le n-1
Esimerkki
Syöte:
3 0 2 1
Tuloste:
1
Selitys: Jonon viimeisenä oleva lapsi ei saa ikinä karkkia.