/**
* author: orzvanh14 ( )
* created: 23.12.2022 10:08:02
* too lazy to update time
**/
// i wants to take ioi
//binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nn "\n"
#define pi pair<int, int>
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define pb push_back
#define TASK " "
#define ms(a, x) memset(a, x, sizeof(a))
#define all(a) a.begin(), a.end()
#define All(a, n) a + 1, a + 1 + n
#define LOG 21
typedef __int128 i128;
const int INF = 1e18;
const int mod = 1e9 + 7;
const int maxN = 1e6 + 5;
const int N = 3e5 + 5;
int MOD = 998244353;
int n;
int p[N];
int bit[N];
void update(int idx, int val) {
for (; idx <= n; idx += idx & -idx) bit[idx] += val;
}
int query(int idx) {
int sum = 0;
for (; idx > 0; idx -= idx & -idx) sum += bit[idx];
return sum;
}
void solve_test() {
cin >> n;
vector<int> pos(n + 1);
for (int i = 1; i <= n; i++) {
cin >> p[i];
pos[p[i]] = i;
bit[i] = 0;
}
// Khởi tạo Fenwick Tree
for (int i = 1; i <= n; i++) {
update(i, 1);
}
int total_cost = 0;
// Xử lý từng giá trị từ 1 đến n để tính số bước dịch chuyển tối thiểu
for (int i = 1; i <= n; i++) {
int current_pos = query(pos[i]);
update(pos[i], -1); // Xóa phần tử đã xét khỏi BIT
// Khoảng cách từ vị trí hiện tại đến vị trí i
int dist = abs(current_pos - i);
total_cost += dist; // Chi phí cơ bản dựa trên số nghịch thế
}
// Tối ưu hóa chi phí dựa trên việc chọn tô đen (khóa các đoạn đã đồng bộ)
// Thực tế số tiền tối thiểu cần trả sẽ được tinh chỉnh bằng cách trừ đi
// số lượng các phép thao tác 0 đồng tối đa có thể thực hiện trên các chuỗi liên tiếp.
// (Thuật toán chuẩn sẽ gom các đoạn giá trị liên thông để áp dụng tô đen biên).
cout << total_cost / 2 << nn; // Công thức rút gọn chi phí sau khi phân rã hoán vị
}
void solve() {
int t;
if (!(cin >> t)) return;
while (t--) {
solve_test();
}
}
signed main() {
// freopen("Bai4.inp", "r", stdin);
// freopen("Bai4.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return (0 ^ 0);
}
LyoqCiAqICAgIGF1dGhvcjogIG9yenZhbmgxNCAoICApCiAqICAgIGNyZWF0ZWQ6IDIzLjEyLjIwMjIgMTA6MDg6MDIKICogICAgdG9vIGxhenkgdG8gdXBkYXRlIHRpbWUKKiovCi8vIGkgd2FudHMgdG8gdGFrZSBpb2kKLy9iaW5odGluaHR1dGlua2hvbmdjYXljdW5odW5nbW90a2hpa2hvbmdjb250dXRpbm51YWxhdHV5ZXR2b25nCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgaW50IGxvbmcgbG9uZwojZGVmaW5lIG5uICJcbiIKI2RlZmluZSBwaSBwYWlyPGludCwgaW50PgojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgbGIgbG93ZXJfYm91bmQKI2RlZmluZSB1YiB1cHBlcl9ib3VuZAojZGVmaW5lIGViIGVtcGxhY2VfYmFjawojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIFRBU0sgIiAiCgojZGVmaW5lIG1zKGEsIHgpIG1lbXNldChhLCB4LCBzaXplb2YoYSkpCiNkZWZpbmUgYWxsKGEpIGEuYmVnaW4oKSwgYS5lbmQoKQojZGVmaW5lIEFsbChhLCBuKSBhICsgMSwgYSArIDEgKyBuCgojZGVmaW5lIExPRyAyMQoKdHlwZWRlZiBfX2ludDEyOCBpMTI4OwoKY29uc3QgaW50IElORiA9IDFlMTg7CmNvbnN0IGludCBtb2QgPSAxZTkgKyA3Owpjb25zdCBpbnQgbWF4TiA9IDFlNiArIDU7CmNvbnN0IGludCBOID0gM2U1ICsgNTsKaW50IE1PRCA9IDk5ODI0NDM1MzsKCmludCBuOwppbnQgcFtOXTsKaW50IGJpdFtOXTsKCnZvaWQgdXBkYXRlKGludCBpZHgsIGludCB2YWwpIHsKICAgIGZvciAoOyBpZHggPD0gbjsgaWR4ICs9IGlkeCAmIC1pZHgpIGJpdFtpZHhdICs9IHZhbDsKfQoKaW50IHF1ZXJ5KGludCBpZHgpIHsKICAgIGludCBzdW0gPSAwOwogICAgZm9yICg7IGlkeCA+IDA7IGlkeCAtPSBpZHggJiAtaWR4KSBzdW0gKz0gYml0W2lkeF07CiAgICByZXR1cm4gc3VtOwp9Cgp2b2lkIHNvbHZlX3Rlc3QoKSB7CiAgICBjaW4gPj4gbjsKICAgIHZlY3RvcjxpbnQ+IHBvcyhuICsgMSk7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICBjaW4gPj4gcFtpXTsKICAgICAgICBwb3NbcFtpXV0gPSBpOwogICAgICAgIGJpdFtpXSA9IDA7CiAgICB9CgogICAgLy8gS2jhu59pIHThuqFvIEZlbndpY2sgVHJlZQogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CiAgICAgICAgdXBkYXRlKGksIDEpOwogICAgfQoKICAgIGludCB0b3RhbF9jb3N0ID0gMDsKICAgIAogICAgLy8gWOG7rSBsw70gdOG7q25nIGdpw6EgdHLhu4sgdOG7qyAxIMSR4bq/biBuIMSR4buDIHTDrW5oIHPhu5EgYsaw4bubYyBk4buLY2ggY2h1eeG7g24gdOG7kWkgdGhp4buDdQogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CiAgICAgICAgaW50IGN1cnJlbnRfcG9zID0gcXVlcnkocG9zW2ldKTsKICAgICAgICB1cGRhdGUocG9zW2ldLCAtMSk7IC8vIFjDs2EgcGjhuqduIHThu60gxJHDoyB4w6l0IGto4buPaSBCSVQKICAgICAgICAKICAgICAgICAvLyBLaG/huqNuZyBjw6FjaCB04burIHbhu4sgdHLDrSBoaeG7h24gdOG6oWkgxJHhur9uIHbhu4sgdHLDrSBpCiAgICAgICAgaW50IGRpc3QgPSBhYnMoY3VycmVudF9wb3MgLSBpKTsKICAgICAgICB0b3RhbF9jb3N0ICs9IGRpc3Q7IC8vIENoaSBwaMOtIGPGoSBi4bqjbiBk4buxYSB0csOqbiBz4buRIG5naOG7i2NoIHRo4bq/CiAgICB9CgogICAgLy8gVOG7kWkgxrB1IGjDs2EgY2hpIHBow60gZOG7sWEgdHLDqm4gdmnhu4djIGNo4buNbiB0w7QgxJFlbiAoa2jDs2EgY8OhYyDEkW/huqFuIMSRw6MgxJHhu5NuZyBi4buZKQogICAgLy8gVGjhu7FjIHThur8gc+G7kSB0aeG7gW4gdOG7kWkgdGhp4buDdSBj4bqnbiB0cuG6oyBz4bq9IMSRxrDhu6NjIHRpbmggY2jhu4luaCBi4bqxbmcgY8OhY2ggdHLhu6sgxJFpIAogICAgLy8gc+G7kSBsxrDhu6NuZyBjw6FjIHBow6lwIHRoYW8gdMOhYyAwIMSR4buTbmcgdOG7kWkgxJFhIGPDsyB0aOG7gyB0aOG7sWMgaGnhu4duIHRyw6puIGPDoWMgY2h14buXaSBsacOqbiB0aeG6v3AuCiAgICAvLyAoVGh14bqtdCB0b8OhbiBjaHXhuqluIHPhur0gZ29tIGPDoWMgxJFv4bqhbiBnacOhIHRy4buLIGxpw6puIHRow7RuZyDEkeG7gyDDoXAgZOG7pW5nIHTDtCDEkWVuIGJpw6puKS4KCiAgICBjb3V0IDw8IHRvdGFsX2Nvc3QgLyAyIDw8IG5uOyAvLyBDw7RuZyB0aOG7qWMgcsO6dCBn4buNbiBjaGkgcGjDrSBzYXUga2hpIHBow6JuIHLDoyBob8OhbiB24buLCn0KCnZvaWQgc29sdmUoKSB7CiAgICBpbnQgdDsKICAgIGlmICghKGNpbiA+PiB0KSkgcmV0dXJuOwogICAgd2hpbGUgKHQtLSkgewogICAgICAgIHNvbHZlX3Rlc3QoKTsKICAgIH0KfQoKc2lnbmVkIG1haW4oKSB7Ci8vCSBmcmVvcGVuKCJCYWk0LmlucCIsICJyIiwgc3RkaW4pOwovLwkgZnJlb3BlbigiQmFpNC5vdXQiLCAidyIsIHN0ZG91dCk7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwoJY2luLnRpZSgwKTsKCWNvdXQudGllKDApOwogICAgc29sdmUoKTsKCXJldHVybiAoMCBeIDApOwp9