#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
const int N = 5e4 + 10;
int p[N], a[N], f[N], n;
struct Edge { int u, v, w; };
vector<Edge> e;

int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }

bool cmp(Edge x, Edge y)
{
	return x.w < y.w;
}

int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		e.clear();
		scanf("%d", &n);
		_for(i, 1, n) scanf("%d", &p[i]), a[p[i]] = i, f[i] = i;

		int t = sqrt(n);
		_for(i, 1, n)
		{
			_for(j, i + 1, n)
			{
				if(j - i > t) break;
				ll cur = 1LL * abs(i - j) * abs(p[i] - p[j]);
				if(cur <= n - 1) e.push_back({i, j, cur});
			}
			
			_for(j, p[i] + 1, n)
			{
				if(j - p[i] > t) break;
				ll cur = 1LL * abs(i - a[j]) * abs(p[i] - j);
				if(cur <= n - 1) e.push_back({i, a[j], cur});
			}
		}

		ll ans = 0;
		sort(e.begin(), e.end(), cmp);
		for(auto [u, v, w]: e)
		{
			int fu = find(u), fv = find(v);
			if(fu != fv)
			{
				f[fu] = fv;
				ans += w;
			}
		}
		printf("%lld\n", ans);
	}

	return 0;
}