#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int z;
    cin >> z;

    while(z--) {
        int n;
        cin >> n;
        unordered_set<int> bars;
        vector<int> taxes(n);

        for(int i = 0; i < n; ++i) {
            cin >> taxes[i];
        }

        stack<pair<int, int>> s;
        s.push({0, n-1});
        bars.insert(0);
        bars.insert(n-1);
        while(!s.empty()) {
            auto [l, r] = s.top();
            s.pop();

            int ij = r - l;
            int suma_1 = ij * taxes[l] + ij * taxes[r];

            int mm = -1;
            int max_sum = 0;

            for(int m = l + 1; m < r; ++m) {
                int i = m - l;
                int j = r - m;
                int suma_2 = taxes[l]*i + taxes[r]*j + taxes[m]*(i+j);
                if(suma_2 > suma_1) {
                    if(suma_2 > max_sum) {
                        mm = m;
                        max_sum = suma_2;
                    }
                }
            }
            if(mm != -1) {
                bars.insert(mm);
                s.push({l, mm});
                s.push({mm, r});
            }
        }

        long long ans = 0;

        int L = taxes[0];

        for(int i = 1; i < n; ++i) {
            ans += L;
            if(bars.count(i) != 0) {
                L = taxes[i];
            }
        }

        int R = taxes[n-1];

        for(int i = n-2; i >= 0; --i) {
            ans += R;
            if(bars.count(i) != 0) {
                R = taxes[i];
            }
        }

        cout << ans << endl;
    }

    return 0;
}