#include<iostream>
#include<cassert>
#include<vector>
using namespace std;
int solve(vector<int> v) {
vector<int> overhead(2,0);
int num_of_moves = 0, sum = 0;
for(int i = 0; i < v.size(); i++) {
num_of_moves += overhead[i % 2];
int left = abs(v[i]);
if((sum > 0 && v[i] < 0) || (sum < 0 && v[i] > 0)) {
int used = min(abs(sum), abs(v[i]));
int diff = min(overhead[(i + 1) % 2], used);
overhead[(i + 1) % 2] -= diff;
overhead[i % 2] -= min(overhead[i % 2], (used - diff));
left -= used;
}
sum += v[i];
overhead[(i + 1) % 2] += abs(left);
}
assert(sum == 0);
return num_of_moves;
}
int main() {
cout << solve({-8,-5,0,-3,8,8,2,-2}) << '\n';
cout << solve({-1, -1, 0, 1, 1}) << '\n';
cout << solve({-6, 16, 0, -10});
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNhc3NlcnQ+CiNpbmNsdWRlPHZlY3Rvcj4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBzb2x2ZSh2ZWN0b3I8aW50PiB2KSB7Cgl2ZWN0b3I8aW50PiBvdmVyaGVhZCgyLDApOwoJaW50IG51bV9vZl9tb3ZlcyA9IDAsIHN1bSA9IDA7Cglmb3IoaW50IGkgPSAwOyBpIDwgdi5zaXplKCk7IGkrKykgewoJCW51bV9vZl9tb3ZlcyArPSBvdmVyaGVhZFtpICUgMl07CgkJaW50IGxlZnQgPSBhYnModltpXSk7CgkJaWYoKHN1bSA+IDAgJiYgdltpXSA8IDApIHx8IChzdW0gPCAwICYmIHZbaV0gPiAwKSkgewoJCQlpbnQgdXNlZCA9IG1pbihhYnMoc3VtKSwgYWJzKHZbaV0pKTsKCQkJaW50IGRpZmYgPSBtaW4ob3ZlcmhlYWRbKGkgKyAxKSAlIDJdLCB1c2VkKTsKCQkJb3ZlcmhlYWRbKGkgKyAxKSAlIDJdIC09IGRpZmY7CgkJCW92ZXJoZWFkW2kgJSAyXSAtPSBtaW4ob3ZlcmhlYWRbaSAlIDJdLCAodXNlZCAtIGRpZmYpKTsKCQkJbGVmdCAtPSB1c2VkOwoJCX0KCQlzdW0gKz0gdltpXTsKCQlvdmVyaGVhZFsoaSArIDEpICUgMl0gKz0gYWJzKGxlZnQpOwoJfQoJCglhc3NlcnQoc3VtID09IDApOwoJcmV0dXJuIG51bV9vZl9tb3ZlczsKfQoKaW50IG1haW4oKSB7Cgljb3V0IDw8IHNvbHZlKHstOCwtNSwwLC0zLDgsOCwyLC0yfSkgPDwgJ1xuJzsKCWNvdXQgPDwgc29sdmUoey0xLCAtMSwgMCwgMSwgMX0pIDw8ICdcbic7Cgljb3V0IDw8IHNvbHZlKHstNiwgMTYsIDAsIC0xMH0pOwp9Cg==