Untitled

#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define sz(v) (v.size())
#define yes cout<<"Yes"<<'\n';
#define no cout<<"No"<<'\n';
#define endl '\n';
#define f(i,j,k) for(long long i=j;i<k;i++)
#define fb(i,j,k) for(long long i=j;i>=k;i--)
#define fs(i,j,k,p) for(long long i=j;i<k;i+=p)
#define fbs(i,j,k,p) for(long long i=j;i>=k;i-=p)
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define pi 3.141592653589793238462
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<int>> vvi;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pp ;
typedef vector<ll> vll;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
long long pow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
ll mod =1e9+7;

void add_divs(ll x, map<ll, ll>&divs){
    ll i = 2;
    while(i * i <= x){
        while (x % i == 0){
            divs[i]++;
            x /= i;
        }
        i++;
    }
    if(x > 1) divs[x]++;
}




ll n1;

ll mrg (ll x ,ll y )
{
    return min(x,y);
}

struct segment_tree
{
    vector<ll> tree;
    void clear()
    {
        tree.clear();
    }

    void init(int num, const vector<ll>& a)
    {
        n1 = num;
        tree.assign(4 * n1, 1e18);
        build(a);
    }

    void build(const vector<ll>& a, int id=0,int ns = 0, int ne = n1-1)
    {
        if(ns==ne){
            tree[id] = a[ns];
            return ;
        }
        int l = 2*id+1;
        int r = l+1;
        int md = ns+(ne-ns)/2;
        build(a,l, ns, md);
        build(a,r, md+1, ne);
        tree[id] = mrg(tree[l],tree[r]);
    }


    ll query(int qs, int qe, int id=0, int ns=0, int ne=n1-1)
    {
        if(ns>qe || qs>ne){
            return 1e18; ///infnity
        }
        if(qs<=ns && qe>=ne){
            return tree[id];
        }
        int l = 2*id+1;
        int r = l+1;
        int md = ns+(ne-ns)/2;
        ll ndl = query(qs, qe, l, ns, md);
        ll ndr = query(qs, qe,r, md+1,ne);
        return mrg(ndl,ndr );
    }

    void upd(int pos , int val , int id=0, int ns=0,int ne=n1-1)
    {
        if(ns>pos || pos>ne){
            return;
        }
        if(ns==ne){
            tree[id]=val;
            return ;
        }
        int l = 2*id+1;
        int r = l+1;
        int md = ns+(ne-ns)/2;
        upd(pos, val,l, ns, md);
        upd(pos, val, r, md+1, ne);
        tree[id] = mrg(tree[l],tree[r]);
    }
} st ;
auto bin(long long n,vector<int> &v)
{
    long long i;
    v.push_back(0);
    for (i = 1 << 30; i > 0; i = i / 2)
    {
        if((n & i) != 0)
        {
            v.push_back(1);
        }
        else
        {
            v.push_back(0);
        }
    }
    return v;
}

vector<bool> premier(int x)
{
    vector<bool> pre(x+1,0);
    for(int i=2;i<x+1;i++)
    {
        if(!pre[i])
        {
            for(int j=2*i;j<=x;j+=i)
            {
                pre[j]=1;
            }
        }
    }
    return pre;
}
ll mult(ll a,ll b,ll n)
{
    return((a%n)*(b%n))%n;
}
ll sum(ll a,ll b,ll n)
{
    return((a%n)+(b%n))%n;
}
ll sub(ll a,ll b,ll n)
{
    return((a%n)-(b%n)+n)%n;
}
ll inv(ll a,ll n)
{
    return pow(a,n-2,n);
}
vector<ll> ff()
{
    int n=61;
    vector<ll> vv(n+1);
    vv[0]=2;
    ll j=2;
    for (int i=1;i<=n;i++)
    {
        vv[i]=0;
        vv[i]+=vv[i-1]+j;
        j*=2;
    }
    for (int i=1;i<=n;i++)
    {
        vv[i]+=vv[i-1];
    }
    return vv;
}
int xxxxx=2*1000000+1;
vector<ll> fact(xxxxx);
vector<ll> invfact(xxxxx);
void fac(ll n=mod)
{
    fact[0]=fact[1]=1;
    for (int i =2;i<xxxxx;i++)
        fact[i]=mult(fact[i-1],i,n);
}
void invfac(ll n=mod)
{
    invfact[xxxxx-1]=inv(fact[xxxxx-1],n);
    for (int i =xxxxx-2;i>=0;i--)
        invfact[i]=mult(invfact[i+1],i+1,n);
}
ll C(ll k,ll m,ll n=mod)
{
    if ((k>m)||(k<0))
        return 0;
    if (k==0)return 1;
    return mult(fact[m],mult(invfact[k],invfact[m-k],n),n);
}
void prep(ll n=mod)
{
    fac(n);
    invfac(n);
}
ll A(ll k, ll m, ll n)
{
    if ((k>m)||(k<0))
        return 1;
    return mult(fact[m],invfact[k],n);
}
#define INF 1000000000000000000


void dijkstra(vector<vector<pp>>& graph, ll source) {
    ll n = graph.size(); // Number of vertices
    vector<ll> dist(n, INF); // Initialize distances to infinity
    priority_queue<pp, vector<pp>, greater<pp>> pq; // Min-heap for priority queue

    dist[source] = 0; // Distance from source to itself is 0
    pq.push({0, source}); // Push the source vertex into the priority queue

    while (!pq.empty()) {
        ll u = pq.top().second; // Extract vertex with minimum distance
        ll d = pq.top().first; // Extracted distance
        pq.pop();

        // Check all neighbors of u
        for (auto& neighbor : graph[u]) {
            ll v = neighbor.first; // Neighbor vertex
            ll w = neighbor.second; // Edge weight from u to v

            // Relaxation step
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w; // Update distance if a shorter path is found
                pq.push({dist[v], v}); // Push the updated distance and vertex to the priority queue
            }
        }
    }

    cout <<  dist[n-1] << endl;
    /*for (int i = 0; i < n; ++i) {
        cout << "Shortest distance from source to vertex " << i << " is " << dist[i] << endl;
    }*/
}
bool sortbycond(const pair<int, int>& a,
                const pair<int, int>& b)
{
    if (a.first != b.first)
        return (a.first < b.first);
    else
        return (a.second > b.second);
}
int s(int n) {

    int sum = 0;
    string ss = to_string(n);
    for (char c : ss) {
        sum += c - '0';
    }
    return sum;
}


int sum(int n) {

    if (n == 0) return 0;
    if (n % 10 != 9) return sum(n - 1) + s(n);
    int k=n/10;
    return 10*sum(k)+45*(k + 1);
}
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e18
#define nline "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
const int N = 1e6;
int mobius[N + 10];
bool prime[N + 1];
void sieve()
{
    int n=1e6;
    memset(prime, true, sizeof(prime));
    for (int p = 2; p * p <= n; p++) {

        if (prime[p] == true) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
}
#define int long long
// Function to precompute the Mobius function
void precompute_mobius()
{
    for (int i = 1; i <= N; i++) {
        mobius[i] = 1;
    }
    for (int i = 2; i <= N; i++) {
        if (prime[i]) {
            for (int j = i; j <= N; j += i) {
                if (j % (i * i) == 0) {
                    mobius[j] = 0;
                }
                else {
                    mobius[j] *= -1;
                }
            }
        }
    }
}
struct  edge{
    int a,b,w;
    edge()
    {
        a=0;
        b=0;
        w=0;
    }
    edge(int a1,int b1,int w1)
    {
        a=a1;
        b=b1;
        w=w1;
    }
    bool  operator <(const edge &other1)
    {
        return (w<other1.w);
    }
};
ll c2(ll n)
{
    return (n*(n-1))/2;
}
int sum(int i,int j,int *prf)
{
    if (i==0)return prf[j];
    return prf[j]-prf[i-1];
}
void solve()
{
    int n;
    cin>>n;
    vector<int>a(n);
    for (auto &x:a)cin>>x;
    segment_tree st;
    vector<int>dp(n);
    dp[n-1]=a[n-1];
    int output=a[n-1];
    int prf[n];prf[0]=a[0];
    for (int i=1;i<n;++i)prf[i]=a[i]+prf[i-1];
    vector<int>b(n);
    for(int i=0;i<n;++i)b[i]=a[i]+i;
    st.init(n,b);
    for (int i=n-2;i>=0;i--)
    {
        int res=st.query(i+1,n-1);
        if (res>b[i])
        {
            int x=i;
            int right=a[i],left=max(a[i]+i-n,0ll);
            dp[i]=((right-left+1)*(right+left))/2;
        }
        else
        {
            ll l=i+1,r=n-1,mid,ans;
            while(l<=r)
            {
                mid=(l+r)/2;
                if (st.query(i+1,mid)<=b[i])
                {
                    ans=mid;
                    r=mid-1;
                }
                else
                    l=mid+1;
            }
            int x=a[i];
            int te=1;
            ll left=a[i],right=(a[i]-ans+1);
            dp[i]=(left+right)*(left-right)/2;
            dp[i]+=dp[ans];
            dp[i]=max(dp[i],te);
        }
        output=max(output,dp[i]);

    }
    debug(dp)
    cout<<output<<'\n';
}
signed  main() {
#ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
#endif

    fastio();
    int t;
    t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
}