from collections import deque


t = int(input())
for _ in range(t):
    n = int(input())
    p = list(map(lambda x: int(x) - 1, input().split()))

    ft = [0] * n
    def ft_add(p: int, v: int):
        p += 1
        while p <= n:
            ft[p - 1] += v
            p += -p & p
    def ft_sum(r: int):
        s = 0
        while r:
            s += ft[r - 1]
            r -= -r & r
        return s

    inv = 0
    a = deque()
    for i, v in enumerate(p):
        l = ft_sum(p[i])
        r = i - l
        ft_add(p[i], 1)
        ok_l = l <= r
        ok_r = l >= r
        if ok_l and ok_r:
            if a and a[0] < p[i]:
                a.append(p[i])
            else:
                a.appendleft(p[i])
        elif ok_l:
            a.appendleft(p[i])
        elif ok_r:
            a.append(p[i])
        else:
            assert False
        inv += min(l, r)
    
    ans = list(a)
    
    for i in range(n):
        ans[i] += 1
    
    print(inv)
    print(*ans)