CSES - Jono
  • 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.