#include #include #include #include #include using namespace std; void solve() { int n; cin >> n; vector a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; } int ans = -1; for(int i = 0; i < n; ++i) { vector indicies; for(int j = 0; j < n; ++j) { if(i != j) { indicies.push_back(j); } } do { vector taken(n, false); int sum = 0; for(int k = 0; k < (int) indicies.size(); ++k) { taken[indicies[k]] = true; int l = indicies[k] - 1; int r = indicies[k] + 1; while(l >= 0 and taken[l] == true) { l -= 1; } while(r < n and taken[r] == true) { r += 1; } if(l < 0 and r >= n) { sum += a[indicies[k]]; } else if(l >= 0 and r >= n) { sum += a[l]; } else if(l < 0 and r < n) { sum += a[r]; } else { sum += a[l] * a[r]; } } sum += a[i]; ans = max(ans, sum); } while(next_permutation(indicies.begin(), indicies.end())); } cout << ans << 'n'; } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int t; cin >> t; while(t--) { cout << "#" << t + 1 << ' '; solve(); } return 0; } /* 10 9 1 2 3 4 5 6 7 8 9 9 1 2 3 4 5 6 7 8 9 9 1 2 3 4 5 6 7 8 9 9 1 2 3 4 5 6 7 8 9 9 1 2 3 4 5 6 7 8 9 9 1 2 3 4 5 6 7 8 9 9 1 2 3 4 5 6 7 8 9 9 1 2 3 4 5 6 7 8 9 9 1 2 3 4 5 6 7 8 9 9 1 2 3 4 5 6 7 8 9 */ /* 10 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 */