1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int a[500500];
vector<int> nbh[500500];
bool visied[500500];

int dfs(int v) {
    int s = 0;
    if(!visied[v]) {
        visied[v] = true;
        s += a[v];
        for(auto u: nbh[v]) {
            s += dfs(u);
        }
    }

    return s;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    bool positive = true;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        if(a[i] < 0) {
            positive = false;
        }
    }

    if(positive) {
        cout << "0\n";
        return 0;
    }

    ll states = 0;

    int best = 1e9;

    for(ll i = 1; i < 1<<(n-1); i++) {
        ll c = (i>>1)^i;
        ll p = ((i-1)>>1)^(i-1);
        ll s = c^p;

        ll j;
        for(j = 0; j < n-1; j++) {
            if((s>>j)&1) {
                break;
            }
        }

        if(states&s) {
            states &= ~s;

            nbh[j].erase(std::remove(nbh[j].begin(), nbh[j].end(), j+1), nbh[j].end()); 
            nbh[j+1].erase(std::remove(nbh[j+1].begin(), nbh[j+1].end(), j), nbh[j+1].end()); 
        } else {
            states |= s;

            nbh[j].push_back(j+1);
            nbh[j+1].push_back(j);
        }

        for(ll k = 0; k < n; k++) {
            visied[k] = false;
        }

        bool trigger = true;
        for(ll k = 0; k < n; k++) {
            if(dfs(k) < 0) {
                trigger = false;
                break;
            }
        }
        
        if(trigger) {
            int cnt = 0;
            for(ll k = 0; k < n; k++) {
                cnt += nbh[k].size();
            }
            cnt /= 2;
            best = min(best, cnt);
        }
    }

    if(best == 1e9) {
        best = -1;
    }

    cout << best << "\n";

    return 0;
}