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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <vector>
#include <algorithm>

#define LL long long 

using namespace std;

const int MAX_WARTOSC = 1e9;

template <class T>
class DrzewoMinimow {
private: 
	int wielkosc;
	T *tab;
	
	int pozycja(int i) {
		return wielkosc / 2 + i - 1;
	}

public:
	DrzewoMinimow(int n) {
		wielkosc = 1;
		while (wielkosc < n)
			wielkosc *= 2;
		wielkosc *= 2;
		tab = new T[wielkosc];
		for (int i = 0; i < wielkosc; ++i)
			tab[i] = MAX_WARTOSC;
	}
	
	~DrzewoMinimow() {
		delete[] tab;
	}
	
	void dodaj(T war, int poz) {
		poz = pozycja(poz);
		tab[poz] = war;
		poz /= 2;
		while (poz >= 1) {
			tab[poz] = min(tab[2 * poz], tab[2 * poz + 1]); 
			poz /= 2;
		}
	}

	void usun(int poz) {
		dodaj(MAX_WARTOSC, poz);
	}
	
	T min_przedzial(int pocz, int kon) {
        pocz = pozycja(pocz);
        kon = pozycja(kon);
        T mi = min(tab[pocz], tab[kon]);
        while (pocz + 1 < kon) {
            if (pocz % 2 == 0) 
                mi = min(mi, tab[pocz + 1]);
            if (kon % 2 == 1)
                mi = min(mi, tab[kon - 1]);
            pocz /= 2;
            kon /= 2;
        }
        return mi;
    }
};

int main() {
	int i, j, n, a;
	const int MAX = 1000000000;
	scanf("%d", &n);
	vector<pair<int, int>> elem;
	for (i = 0; i < n; ++i) {
		scanf("%d", &a);
		if (a != 0)
			elem.push_back(make_pair(a, i)); // niezerowe elementy
	}
	
	vector<LL> sums, sums_srt, sums_unique;
	LL sum = 0;
	for (i = 0; i < elem.size(); ++i) {
		if (i == 0)
			sums.push_back(0);
		else
			sums.push_back(-sum);
		sum += elem[i].first;
	}
	sort(sums.begin(), sums.end());
	for (i = 0; i < elem.size(); ++i)
		if (i == 0 || sums[i] != sums[i - 1])
			sums_unique.push_back(sums[i]);
			
	DrzewoMinimow<int> d(sums_unique.size() + 4);
	
	vector<int> wyn(elem.size(), 0);
	int sum_dist = 0;
	sum = 0;
	for (i = 0; i < elem.size(); ++i) { 
		int ps = distance(sums_unique.begin(), lower_bound(sums_unique.begin(), sums_unique.end(), -sum)) + 1;
		sum += elem[i].first;
		int val = d.min_przedzial(ps, ps);
		int new_val = 0;
		if (i == 0) {
			d.dodaj(0, ps);
		} else {
			sum_dist += elem[i].second - elem[i - 1].second;
			if (wyn[i - 1] >= 0) {
				new_val = -sum_dist + wyn[i - 1];
				if (new_val < val)
					d.dodaj(new_val, ps);
			}
		}
		int zero_ps = distance(sums_unique.begin(), lower_bound(sums_unique.begin(), sums_unique.end(), -sum)) + 1;
		val = d.min_przedzial(zero_ps, sums_unique.size() + 3);
		if (val == MAX_WARTOSC)
			wyn[i] = -1;
		else
			wyn[i] = val + sum_dist;
	} 
	if (elem.size() == 0)
		printf("0");
	else
		printf("%d", wyn[elem.size() - 1]);
	return 0;
}