Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: karves.in

Rezultatų failas: karves.out

Jei norite pateikti savo sprendimą - prisijunkite.

Karvės

Rolandas padeda savo seneliui fermoje. Šiandien jam reikia pamelžti karves. Fermoje yra n karvių išrikiuotų į vieną eilę, sunumeruotų nuo 1 iki n iš kairės į dešinę. Kai Rolandas pamelžia karvę, visos karvės, mačiusios dabartinę karvę išsigąsta ir praranda 1 vienetą pieno. Karvė, atsisukusi į kairę, mato visas karves su mažesniu indeksu nei jos, o karvė, atsisukusi į dešinę, mato visas karves su indeksu didesniu nei jos. Jau išgąsdinta karvė gali dar kartą išsigąsti ir prarasti dar vieną pieno vienetą. Karvė, kuri jau buvo pamelžta, daugiau išsigąsti negali. Galima tarti, jog karvė niekada nepraras viso pieno.

Rolandas gali nuspręsti, kokia tvarka jis pamelš karves, bet kiekvieną karvę jam reikia pamelžti būtent vieną kartą. Rolandas nori prarasti kuo mažiau pieno. Išveskite minimalų kiekį, kiek Rolandas praras pieno.

Pradiniai duomenys

Pirmoje eilutėje yra skaičius n (1\\leqn\\leq200000).

Antroje eilutėje yra n skaičių a_i, kur a_i yra 0, jei karvė atsisukusi į kairę, arba 1, jei karvė atsisukusi į dešinę.

Rezultatai

Išveskite vieną skaičių - minimalų kiekį, kiek Rolandas praras pieno.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4
0 0 1 0
 
1
 
5
1 0 1 0 1
 
3