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.

#include <bits/stdc++.h>
using namespace std;

int sp[100001];  // a[0], a[1], a[2], a[3]...., a[999];
int n;
int k;     // nr de cifre 1 din sir

int main()
{
    int x;
    // citirea sirului
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> x;
        sp[i] = sp[i - 1] + x;
    }
    
    k = sp[n];
    
    int smax = 0;
    for (int i = k; i <= n; ++i)
        if (sp[i] - sp[i - k] > smax)
            smax = sp[i] - sp[i - k];
            
    cout << k - smax;
    
    return 0;
    
}