#include <bits/stdc++.h>
#define V vector
#define Vi vector<int>
#define sz(a) ((int)a.size())
#define fi first
#define se second
#define Int pair<int, int>
#define Inf ((int)1e18)
#define pb push_back
#define ins insert
#define For(i, x, y) for (int i = (x); i <= (y); i++)
#define Rep(i, x, y) for (int i = (x); i >= (y); i--)
#define seg int p, int l, int r
#define lid p << 1, l, mid
#define all(a) a.begin(), a.end()
#define rid p << 1 | 1, mid + 1, r
#define mid ((l + r) / 2)
#define Ceil(x, y) ((x + y - 1) / y)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define IO(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
using namespace std;
#define int long long
struct Ace_taffy {
  Ace_taffy(int n) : mn(4 * n + 5, Inf) {}
  void add(seg, int x, int z) {
    if (l == r) {
      mn[p] = z;
      return;
    }
    x <= mid ? add(lid, x, z) : add(rid, x, z);
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
  }
  int ask(seg, int L, int R) {
    if (L > R) return Inf;
    if (l >= L && r <= R) return mn[p];
    return min(L <= mid ? ask(lid, L, R) : Inf, R > mid ? ask(rid, L, R) : Inf);
  }
  Vi mn;
};
signed main() {
#ifndef ONLINE_JUDGE
  IO(1);
#endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int _, n;
  for (cin >> _; cin >> n;) {
    Vi a(n + 5);
    For(i, 1, n) cin >> a[i];
    map<int, int> mp;
    Vi las(n + 5);
    Rep(i, n, 1) {
      las[i] = mp.count(a[i]) ? mp[a[i]] : n + 1;
      mp[a[i]] = i;
    }
    auto calc = [&](int l, int r) { return (l + r) * (r - l + 1) / 2; };
    mp.clear();
    Vi vec;
    int sum = 0;
    For(i, 1, n) {
      if (!mp.count(a[i])) vec.pb(i), sum += calc(i, n);
      mp[a[i]] = 1;
    }
    int ans = sum;
    set<int> ss;
    for (int x : vec) {
      auto it = ss.lower_bound(a[x]);
      if (it != ss.end()) cmin(ans, sum + (*it) - a[x] - calc(x, las[x] - 1));
      if (it != ss.begin()) {
        it--;
        cmin(ans, sum + a[x] - (*it) - calc(x, las[x] - 1));
      }
      ss.ins(a[x]);
    }
    Ace_taffy tr(n);
    sort(all(vec), [&](int x, int y) { return a[x] > a[y]; });
    for (int x : vec) {
      cmin(ans, sum + tr.ask(1, 1, n, x + 1, n) + calc(las[x], n) - a[x]);
      tr.add(1, 1, n, x, a[x] - calc(x, n));
    }
    tr = Ace_taffy(n);
    reverse(all(vec));
    for (int x : vec) {
      cmin(ans, sum + tr.ask(1, 1, n, x + 1, n) + calc(las[x], n) + a[x]);
      tr.add(1, 1, n, x, -a[x] - calc(x, n));
    }
    cout << ans << '\n';
  }
}