ARC 137

template <typename T>
vector<pair<T, int>> runLengthEncode(const vector<T>& input) {
    vector<pair<T, int>> encoded;
    int size = input.size();
    for (int i = 0; i < size; ++i) {
        int count = 1;
        while (i + 1 < size && input[i] == input[i + 1]) {
            ++i;
            ++count;
        }
        encoded.emplace_back(input[i], count);
    }
    return encoded;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vint A(N);
    rep(i, N) cin >> A[i];

    auto ps = runLengthEncode(A);
    if (ps.size() == 1) {
        cout << N + 1 << endl;
        return;
    }

    int m = ps.size();

    int mone = 0, pone = 0;
    bool is_init_one = ps[0].first == 1;
    int s0 = 0, s1 = 1;
    if (is_init_one) swap(s0, s1);
    int sum0 = 0;
    for (int i = s0; i < m; i += 2) {
        sum0 += ps[i].second;
        chmax(pone, sum0);
        if (i + 1 < m) {
            sum0 -= ps[i + 1].second;
            if (sum0 < 0) sum0 = 0;
        }
    }
    int sum1 = 0;
    for (int i = s1; i < m; i += 2) {
        sum1 += ps[i].second;
        chmax(mone, sum1);
        if (i + 1 < m) {
            sum1 -= ps[i + 1].second;
            if (sum1 < 0) sum1 = 0;
        }
    }

    int cnt_one = accumulate(all(A), 0);
    int r = cnt_one + pone;
    int l = cnt_one - mone;
    cout << r - l + 1 << endl;
}