from collections import deque class FenwickTree: def __init__(self, N): self.N = N self.d = [0] * N def add(self, p, x): assert 0 <= p < self.N p += 1 while p <= self.N: self.d[p - 1] += x p += p & (-p) def sum0(self, r): s = 0 while r > 0: s += self.d[r - 1] r -= r & (-r) return s def get_sum(self, l, r): assert 0 <= l <= r <= self.N return self.sum0(r) - self.sum0(l) def solve(): N = int(input()) P = list(map(lambda x: x - 1, map(int, input().split()))) fw = FenwickTree(N) dq = deque() ans = 0 for i in range(N): l = fw.get_sum(0, P[i]) r = fw.get_sum(P[i], N) fw.add(P[i], 1) if l < r: dq.appendleft(P[i] + 1) ans += l elif l > r: dq.append(P[i] + 1) ans += r else: if i == 0: dq.append(P[i] + 1) continue top = dq.popleft() dq.appendleft(top) if P[i] < top: dq.appendleft(P[i] + 1) ans += l else: dq.append(P[i] + 1) ans += r print(ans) print(*dq) T = int(input()) for _ in range(T): solve()