Running Miles

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Pos{
    ll val;
    int pos;
};

int t;

int main(){
    freopen("runningmiles.in", "r", stdin);

    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<ll> left(n);
        vector<ll> right(n);
        vector<ll> arr(n);
        for(int i=0; i<n; i++){
            cin >> arr[i];
        }
        vector<ll> l(n);
        vector<ll> r(n);
        for(int i=0; i<n; i++){
            l[i] = arr[i]-(n-i-1);
            r[i] = arr[i]-i;
        }
        left[0] = l[0];
        //left[0].pos = 0;
        for(int i=1; i<n; i++){
            left[i] = max(left[i-1], l[i]);
            //if(arr[i]>left[i-1].val){
                //left[i].val = arr[i];
                //left[i].pos = i;
            //}else if(arr[i] == left[i-1].val){
                //left[i].val = arr[i];
                //left[i].pos = i;
            //}else{
                //left[i].val = left[i-1].val;
                //left[i].pos = left[i-1].pos;
            //}
        }
        right[n-1] = r[n-1];
        //right[n-1].pos = n-1;
        for(int i=n-2; i>=0; i--){
            right[i] = max(right[i+1], r[i]);
            //if(arr[i]>right[i+1].val){
                //right[i].val = arr[i];
                //right[i].pos = i;
            //}else if(arr[i] == right[i+1].val){
                //right[i].val = arr[i];
                //right[i].pos = i;
            //}else{
                //right[i].val = right[i+1].val;
                //right[i].pos = right[i+1].pos;
            //}
        }
        ll ans = 0;
        for(int i=1; i<n-1; i++){
            ans = max(ans, left[i-1]+arr[i]+right[i+1]+n-1);
            //cout << "left[i-1]: " << left[i-1] << ", arr[i]: " << arr[i] << ", right[i+1]: " << right[i+1] << '\n';
            //cout << "left[i-1].val: " << left[i-1].val << ", left[i-1].pos: " << left[i-1].pos << '\n';
            //cout << "arr[i]: " << arr[i] << ", i: " << i << '\n';
            //cout << "right[i+1].val: " << right[i+1].val << ", right[i+1].pos: " << right[i+1].pos << '\n';
            //cout << "============" << '\n';
        }
        cout << ans << '\n';
    }

    return 0;
}