#include <bits/stdc++.h>
using namespace std;

int main() {
    // your code goes here
    int t;
    if (cin>>t){
        while(t--){
            int n;
            cin>>n;
            vector<int>v(n);
            vector<pair<int,int>>a(n);
            for(int i=0;i<n;i++){
                cin>>v[i];
                a[i]={v[i],i};
            }
            sort(a.begin(),a.end(),greater<pair<int,int>>());
            set<int>s;
            long long sum = 0;
            for (int i=0;i<n;i++){
                int val=a[i].first;
                int id=a[i].second;
                auto it=s.insert(id).first;
                // prev greater and second prev greater than v[i]
                int j1 = -1, j2 = -1;
                auto l=it;
                if (l!=s.begin()){
                    l--;
                    j1 =*l;
                    if (l!=s.begin()){
                        auto ll=l;
                        ll--; 
                        j2=*ll;
                    }
                }
                // next greater and second next greater than v[i]
                int i1 = n, i2 = n;
                auto r = it;
                r++;
                if (r!=s.end()){
                    i1=*r;
                    auto rr=r;
                    rr++; 
                    if (rr!=s.end()){
                        i2=*rr;
                    }
                }
                // # of subarrays where v[i] is 2nd max on right side of array
                int r_sub=0;
                if (i1!=n){
                    int l_way=id-j1;
                    int r_way=i2-i1;
                    r_sub=l_way*r_way;
                }
                // # of subarrays where v[i] is 2nd max on left side of array
                int l_sub=0;
                if (j1!=-1){
                    int l_way=j1-j2;
                    int r_way=i1-id;
                    l_sub=l_way*r_way;
                }
                sum+=(r_sub+l_sub)*val;
            }
            cout<<sum<<endl;
        }
    }
}