Untitled

#include<iostream>
using namespace std;
int T,N,a[1001],visited[1001],s[1001],visited2[1001],res,sum;
void xuat(){
	for (int i=1 ;i<=N-2;i++){
		cout<<s[i]<<" ";
	}
	cout<<endl;
}
void reset(){
	for (int i=1 ;i<=N+1;i++){
		visited2[i]=0;
	}
}

int getMax(){
	int max=-1;
	for (int i=1;i<=N;i++){
		if(!visited2[i]){
			if(max<a[i]) max=a[i];
		}
	}
	return max;
}
int  tinh(int k){
	int sum=0;
	//1 2 3 4 5 6 7 8
	//duyet het s[];
	for (int i=1 ;i<=N-2;i++){
		int idx=s[i];
		visited2[idx]=1;
		int l;
		int r;
		for (int j=idx-1;j>=0;j--){
			if(visited2[j]==0) 
			l=j;
			break;
		}
		for (int j=idx+1;j<=N+1;j++){
			if(visited2[j]==0) 
			r=j;
			break;
		}
		sum=sum+a[r]*a[l];
	}
	sum+=2*getMax();
	return sum;
}
void backtrack(int pos){
	for (int i=1;i<=N;i++){
		if(!visited[i]){
			visited[i]=1;
			s[pos]=i;
			if(pos==N-2){
				reset();
				int value=tinh(0);
				if(value>res) res=value;
			}
			else backtrack(pos+1);
			visited[i]=0;
		}
	}
}
int main(){
	freopen("input.txt","r",stdin);
	cin>>T;
	for (int t=1;t<=T;t++){
		cin>>N;
		for (int i=1;i<=N;i++){
			cin>>a[i];
		}
		a[0]=1;
		a[N+1]=1;
		backtrack(1);
		cout<<res<<endl;
	}
	return 0;
}