OI XXXII - sch

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

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 1000 * 1001;

#define ar std::array

typedef std::vector<std::vector<int64_t>> _kra;
#define int int64_t

ar<int, sizik> a, b, pa, pb, dir;

constexpr int PRAWO = 1, LEWO = -1, NIC = 0;
int sign(int x) {
    if (x > 0) return PRAWO;
    if (x < 0) return LEWO;
    return NIC;
}

int absll(int ax) {
    if (ax > 0) return ax;
    return -ax;
}

void ziomek(int i, std::deque<std::pair<int, int>>& przedzialy, int& Delta, int& ans, int& total_len, bool w_lewo) {
    int dx = 0;
    if (w_lewo) dx = 1;

    int X = a[i + dx];
    int A = absll(pa[i] - pb[i]);

    int Q = A - X;

    if (Q <= 0) {
        przedzialy.clear();
        total_len = 0;
        if (A > 0) {
            przedzialy.push_back({-Delta, -Delta + A});
            total_len = A;
        }
    } else {
        while (!przedzialy.empty()) {
            int len = przedzialy.back().second - przedzialy.back().first;
            if (total_len - len >= Q) {
                total_len -= len;
                przedzialy.pop_back();
            } else {
                int keep = Q - (total_len - len);
                przedzialy.back().second = przedzialy.back().first + keep;
                total_len = Q;
                break;
            }
        }

        int current_end = -Delta;
        int start_pos = -Delta;

        while (X > 0 && !przedzialy.empty()) {
            int next_start = przedzialy.front().first;
            int next_end = przedzialy.front().second;
            int gap = next_start - current_end;

            if (gap < 0) gap = 0;

            if (X <= gap) {
                current_end += X;
                X = 0;
            } else {
                X -= gap;
                current_end = next_end;
                przedzialy.pop_front();
            }
        }

        if (X > 0) {
            current_end += X;
        }

        if (!przedzialy.empty() && current_end >= przedzialy.front().first) {
            przedzialy.front().first = start_pos;
        } else {
            przedzialy.push_front({start_pos, current_end});
        }

        total_len = A;
    }

    if (!przedzialy.empty()) {
        ans = std::max(ans, przedzialy.back().second + Delta);
    }
    Delta++;
}

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

    for (int i = 1; i <= n; i++)
        std::cin >> a[i];
    for (int i = 1; i <= n; i++)
        std::cin >> b[i];

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

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

    for (int i = 1; i < n; i++) {
        dir[i] = sign(pa[i] - pb[i]);
    }

    int ans = 0;

    std::deque<std::pair<int, int>> przedzialy;
    int Delta = 0;
    int total_len = 0;

    for (int i = 1; i < n; i++) {
        if (dir[i] != PRAWO) {
            przedzialy.clear();
            Delta = 0;
            total_len = 0;
            continue;
        }
        ziomek(i, przedzialy, Delta, ans, total_len, false);
    }

    przedzialy.clear();
    Delta = 0;
    total_len = 0;
    for (int i = n - 1; i >= 1; i--) {
        if (dir[i] != LEWO) {
            przedzialy.clear();
            Delta = 0;
            total_len = 0;
            continue;
        }
        ziomek(i, przedzialy, Delta, ans, total_len, true);
    }

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

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}