https://codeforces.com/problemset/problem/2013/D

const int maxn = 2e5+5;
int n, a[maxn], b[maxn];

bool checkmx(int mid){
    for ( int i = 1; i <= n; i++ ) b[i] = a[i];
    for ( int i = 1; i <= n - 1; i++ ){
        if ( b[i] > mid ){
            b[i + 1] += (b[i] - mid);
        }
    }
    return b[n] <= mid;
}

bool checkmn(int mid){
    for ( int i = 1; i <= n; i++ ) b[i] = a[i];
    for ( int i = n; i >= 2; i-- ){
        if ( b[i] < mid ){
            b[i - 1] -= (mid - b[i]);
        }
    }
    return b[1] >= mid;
}

void solve(){
    cin >> n;
    for ( int i = 1; i <= n; i++ ) cin >> a[i];

    int l, r, mid, mx, mn;
    l = 1, r = 1e12;
    while ( l <= r ){
        mid = l + r >> 1;
        if ( checkmx(mid) ){
            mx = mid;
            r = mid - 1;
        }else l = mid + 1;
    }

    l = 1, r = 1e12;
    while ( l <= r ){
        mid = l + r >> 1;
        if ( checkmn(mid) ){
            mn = mid;
            l = mid + 1;
        }else r = mid - 1;
    }

    cout << mx - mn << endl;
}