OI XXXII - sch (Monotonic_queue)

// https://szkopul.edu.pl/problemset/problem/ZssB17GDoiGqYttYNAaEIoOh/site/?key=statement

#include <bits/stdc++.h>

void solve_pass(int n, const std::vector<int64_t>& a, const std::vector<int64_t>& b, int64_t& ans) {
    std::vector<int64_t> PA(n + 1, 0);
    std::vector<int64_t> PB(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        PA[i] = PA[i - 1] + a[i - 1];
        PB[i] = PB[i - 1] + b[i - 1];
    }

    std::vector<bool> flow_right(n + 1, false);
    for (int i = 1; i < n; i++) {
        if (PA[i] > PB[i]) {
            flow_right[i] = true;
        }
    }

    for (int start = 1; start < n;) {
        if (!flow_right[start]) {
            start++;
            continue;
        }

        int end = start;
        while (end < n && flow_right[end]) {
            end++;
        }

        std::deque<int> dq;

        for (int j = start; j <= end + 1; j++) {
            int64_t current_X = PA[j - 1] - j;

            while (!dq.empty()) {
                int back_i = dq.back();
                int64_t back_X = PA[back_i - 1] - back_i;
                if (back_X <= current_X) {
                    dq.pop_back();
                } else {
                    break;
                }
            }
            dq.push_back(j);

            int64_t threshold = PB[j - 1];

            while (!dq.empty()) {
                int front_i = dq.front();
                if (PA[front_i - 1] <= threshold) {
                    dq.pop_front();
                } else {
                    break;
                }
            }

            if (!dq.empty()) {
                int best_i = dq.front();
                int64_t term1 = PA[best_i - 1] - best_i;
                int64_t term2 = j - PB[j - 1];
                ans = std::max(ans, term1 + term2);
            }
        }

        start = end + 1;
    }
}

void solve() {
    int n;
    std::cin >> n;

    std::vector<int64_t> a(n), b(n);
    for (int i = 0; i < n; i++)
        std::cin >> a[i];
    for (int i = 0; i < n; i++)
        std::cin >> b[i];

    if (n == 1) {
        std::cout << "0\n";
        return;
    }

    int64_t ans = 0;

    solve_pass(n, a, b, ans);

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    solve_pass(n, a, b, ans);

    std::cout << ans << std::endl;
}

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

    solve();

    return 0;
}