#include #include #include #include #include #include #include using namespace std; void debug(const string &S, int left, int right, int cnt) { /* string visualized = S.substr(left, right - left); string markers = string(left, ' ') + "^" + string(right - left - 1, ' ') + "^"; cout << S << endl; cout << markers << endl; cout << "Substring: " << visualized << " - Count: " << cnt << endl; */ } int main() { int N; string S; cin >> N >> S; int cnt = 0; int left = 0, right = 1; int ans = 0; for (; right < N + 1; right++) { if (S[right - 1] == '0') cnt--; else cnt++; debug(S, left, right, cnt); if (right - left >= 2) { if (cnt < 0) { assert(S[right - 1] == '0'); S[right - 1] = '1'; cnt += 2; ans++; debug(S, left, right, cnt); int i = 1; while (left < right - 1) { if (S[left] == '0') cnt++; else cnt--; left++; debug(S, left, right, cnt); if (cnt < 0) { bool fixed = false; for (int j = right - i - 1; j > left; j--, i++) { if (S[j] == '0') { S[j] = '1'; cnt += 2; ans++; debug(S, left, right, cnt); fixed = true; i++; break; } } assert(fixed); } } } } } cout << ans << endl; }