Nosaukums
Avīzes Ražošana (avizes_razosana)
Laika limits
1.00s
Atmiņas limits
64.0 MB
Grūtība
83%

Definīcija

Gudrinieku ciemā nedzīvo daudz cilvēku. Bet tie ir ļoti gudri. Tāpēc avīzes rūpnīca tika aprīkota ar robotiem, kas visu darbu veic cilvēku vietā.

Avīzes ražošanas process notiek sekojoši. Viens eksemplārs sastāv no n lapām, kas tiek secīgi izdrukātas vienā rindā. Tomēr rodas viena problēma – dažas lapas ir vērstas ar nepareizo pusi uz augšu. Tāpēc, lai saliktu avīzi pareizi, šīs lapas nepieciešams apgriezt otrādi. Šo darbu veic īpašs robots, kas lapu rindai var vairākkārt pielietot sekojošo operāciju. Robots var izvēlēties vienu lapu, kas vērsta nepareizi, un apgriezt visas lapas, kas atrodas pa labi no tās (ieskaitot izvēlēto). Piemēram, ja pavisam ir 5 lapas, un 3. lapa ir vērsta nepareizi, robots var izpildīt operāciju un apgriezt otrādi 3., 4. un 5. lapas.

Robots patērē daudz enerģijas, tāpēc tam jāstrādā pēc iespējas efektīvi. Aprēķiniet, kāds ir mazākais iespējamais operāciju skaits, lai robots varētu apgriezt visas lapas pareizi!


Ievaddatu raksturojums

Pirmajā rindā dots viens naturāls skaitlis n, viena avīzes eksemplāra lapu skaits (1 ≤ n ≤ 105). Nākamajā rindā doti n skaitļi a1, a2, ... , an: ja ai ir 0, tad i-tā lapa ir vērsta pareizi, ja ai ir 1, tad i-tā lapa ir vērsta nepareizi.


Izvaddatu raksturojums

Izvadiet vienu nenegatīvu veselu skaitli, mazāko operāciju skaitu, kas nepieciešams robotam, lai apgrieztu visas lapas pareizi.


Paraugdati

Stdin
5
0 1 0 1 1
Stdout
3

Stdin
3
0 0 0
Stdout
0

Stdin
4
1 0 0 0
Stdout
2

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