1642D - Repetitions Decoding - CodeForces Solution

def main():
    
    from collections import Counter
    
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        
        cnts = Counter(a)
        flag = 0
        for k, v in cnts.items():
            if v % 2 == 1:                 allans.append([-1])
                flag = 1
                break
        if flag == 1:
            continue
                
        
        moves = []
        lengths = []
                l0 = 0
        while l0 < len(a):
            r0 = l0 + 1
            while r0 < len(a) and a[r0] != a[l0]:
                r0 += 1
            l, r = l0 + 1, r0 + 1
            while l < r0:
                moves.append((r, a[l]))
                moves.append((r, a[l]))
                moves.append((l, a[l]))
                                                for __ in range(4):
                    a.insert(r, a[l])
                for __ in range(2):
                    a.insert(l, a[l])
                l += 3
                r += 5
                r0 += 2
                
                            l = 2 * (r0 - l0)
            lengths.append(l)
            l0 += l
                allans.append([len(moves)])
        allans.extend(moves)
        allans.append([len(lengths)])
        allans.append(lengths)
                    
    
    multiLineArrayOfArraysPrint(allans)
    
    return


import sys
input=sys.stdin.buffer.readline  
def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr):     dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
 
inf=float('inf')
 
from math import gcd,floor,ceil
import math
 
for _abc in range(1):
    main()