#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		vector<long long> a(n+5),mk(n+5);
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		vector<pair<long long,long long>> st;
		for(int i=1;i<=n;i++)
		{
			while(st.size()>=2u and (st[st.size()-1].first-st[st.size()-2].first)*(a[i]-st[st.size()-1].second)-(st[st.size()-1].second-st[st.size()-2].second)*(i-st[st.size()-1].first)>=0)st.pop_back();
			st.emplace_back(i,a[i]);
		}
		for(auto [i,x]:st)
		{
			mk[i]=1;
		}
		long long ans=0;
		int last=0;
		for(int i=1;i<=n;i++)
		{
			if(last)ans+=a[last];
			if(mk[i])last=i;
		}
		last=n+1;
		for(int i=n;i>=1;i--)
		{
			if(last!=n+1)ans+=a[last];
			if(mk[i])last=i;
		}
		cout<<ans<<endl;
	}
	return 0;
}