Pracsiu Dan (dnprx) Se consideră un șir binar a[1], a[2], …, a[n]. Asupra șirului se poate efectua operația swap(i, j) prin care se interschimbă valorile a[i] și a[j].
Cerința
Să se determine numărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații reprezentând elementele șirului binar.
Date de ieșire
Programul va afișa pe ecran numărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir.
Restricții și precizări
1 ≤ n ≤ 100.000
Exemplu:
Intrare
14 1 0 0 1 0 1 1 0 1 0 0 0 1 0
Ieșire
2
Explicație
Se efectuează de exemplu swap(1,5) și swap(13, 8) și astfel șirul devine 0 0 0 1 1 1 1 1 1 0 0 0 0 0, deci valorile de 1 ocupă o zonă continuă. Nu există posibilitatea ca printr-o singură operație să se obțină o secvență continuă de valori de 1.