/***************************************************
* Author  : Anav Prasad
* Handle  : vrangr
* Created : Fri Sep 20 20:31:58 IST 2024
****************************************************/
#include <bits/stdc++.h>

#define debug(...) (void)42
#ifdef LOCAL
    #undef debug
    #include <algo/debug.hpp>
    const bool DEBUG = true;
#else
    [[maybe_unused]] const bool DEBUG = false;
#endif

using namespace std;

typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef __int128_t i128;
#define endl "\n"
#define fastIO ios_base::sync_with_stdio(false),cin.tie(0)
#define TEST int T;cin>>T;while(T--)solve();
#define TEST1 solve();
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(v) ((int)(v).size())
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, forsn, debug, forn)(__VA_ARGS__)
#define forn(i, n) for (__typeof(n) i = 0; i < n; i++)
#define forsn(i, st, end, d) for(__typeof(end) i = st; (d>0?i<=end:i>=end); i+=((__typeof(end))d))
template<typename type>inline void print_vec(const vector<type> &v){rep(i,sz(v))cout<<v[i]<<" \n"[i==sz(v)-1];}
void solve();

int main() {
    fastIO;
    TEST;
#ifdef LOCAL
    cout << "\nTime elapsed: " << (double)clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

// Based on https://codeforces.com/blog/entry/18051
class segtree {
public:
    ll n, h;
    vector<ll> tree, d;
    segtree(ll gn) {
        if (__builtin_popcountll(gn) != 1ll)
            gn = (1ll << (64ll-__builtin_clzll(gn)));
        n = gn;
        gn<<=1ll;
        tree.assign(gn,0ll);
        d.assign(gn,LLONG_MIN);
        h = 64ll-__builtin_clzll(gn);
    }

    void calc(ll p, ll k) {
        if (d[p] == 0) tree[p] = tree[p<<1ll] + tree[p<<1|1];
        else tree[p] = d[p] * k;
    }

    void apply(ll p, ll value, ll k) {
        tree[p] = value * k;
        if (p < n) d[p] = value;
    }

    void build(ll l, ll r) {
        ll k = 2;
        for (l += n, r += n-1ll; l > 1ll; k <<= 1ll) {
            l >>= 1ll, r >>= 1ll;
            for (ll i = r; i >= l; --i) calc(i, k);
        }
    }

    void push(ll l, ll r) {
        ll s = h, k = 1 << (h-1);
        for (l += n, r += n-1; s > 0; --s, k >>= 1ll)
            for (ll i = l >> s; i <= r >> s; ++i) if (d[i] != 0) {
                apply(i<<1, d[i], k);
                apply(i<<1|1, d[i], k);
                d[i] = 0;
            }
    }

    void modify(ll l, ll r, ll value) {
        if (value == 0) return;
        push(l, l + 1);
        push(r - 1, r);
        ll l0 = l, r0 = r, k = 1;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) {
            if (l&1) apply(l++, value, k);
            if (r&1) apply(--r, value, k);
        }
        build(l0, l0 + 1);
        build(r0 - 1, r0);
    }

    ll query(ll l, ll r) {
        push(l, l + 1);
        push(r - 1, r);
        ll res = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l&1) res += tree[l++];
            if (r&1) res += tree[--r];
        }
        return res;
    }
};

void solve() {
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    segtree seg(n);
    rep(i,n) {
        if (i == 0 || seg.query(i-1,i) <= a[i]) {
            seg.modify(i,i+1,a[i]);
            continue;
        }
        ll low = 0ll, high = i-1ll;
        while(low < high) {
            ll mid = (low+high)/2ll;
            ll sum = seg.query(mid,i);
            if ((sum+a[i])/(i-mid+1ll) <= seg.query(mid,mid+1ll))
                high = mid;
            else low = mid+1ll;
        }
        assert(high < i);
        ll sum = seg.query(high,i)+a[i], ct = i-high+1ll;
        ll rem = sum%ct, avg = sum/ct;
        seg.modify(high,high+ct-rem,avg);
        if (rem) {
            seg.modify(high+ct-rem,i+1ll,avg+1ll);
            assert(i+1ll-(high+ct-rem) == rem);
        }
        if (high) assert(seg.query(high-1ll,high) <= seg.query(high,high+1ll));
    }
    cout << seg.query(n-1ll,n) - seg.query(0,1) << endl;
}