How C

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
#define ll long long

ll n,a[N],pre[N],suf[N][3],ans;

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],pre[i]=pre[i-1]+a[i];
	for(int i=1;i<=n;i++){
		suf[i][1]=i-i*i+pre[i-1];
		suf[i][2]=i*i+i-pre[i];
	}
	for(int i=2;i<=n;i++) suf[i][1]=max(suf[i][1],suf[i-1][1]);
	for(int i=n-1;i>=1;i--) suf[i][2]=max(suf[i][2],suf[i+1][2]);
	ans=pre[n];
	for(int i=1;i<=n;i++){
		ans=max(ans,pre[n]+suf[i][1]+suf[i][2]);
	}
	cout<<max(ans,pre[n])<<'\n';
	for(int i=0;i<=n+10;i++){
		pre[i]=0;
		suf[i][1]=0;
		suf[i][2]=0;
	}
	ans=0;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	ll __;
	cin>>__;
	while(__--) solve();
	
	return 0;
}