Read problems statements in Vietnamese  .

Chef likes to work with arrays a lot. Today he has an array A of length N consisting of positive integers. Chef's little brother likes to follow his elder brother, so he thought of creating an array B of length N. The little brother is too small to think of new numbers himself, so he decided to use all the elements of array A to create the array B. In other words, array B is obtained by shuffling the elements of array A.

The little brother doesn't want Chef to know that he has copied the elements of his array A. Therefore, he wants to create the array B in such a way that the Hamming distance between the two arrays A and B is maximized. The Hamming distance between A and B is the number of indices i (1 ≤ i ≤ N) such that A_{i} ≠ B_{i}.

The brother needs your help in finding any such array B. Can you please find one such array for him?

Note that it's guaranteed that no element in A appears more than twice, i.e. frequency of each element is at most 2.

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer N denoting the length of the array A.
The second line contains N space-separated integers A_{1}, A_{2} ... A_{N}.

------ Output ------ 

For each test case, print two lines.
The first line should contain the maximum possible Hamming distance that array B can have from array A.
The second line should contain N space-separated integers denoting the array B; the i-th integer should denote the value of B_{i}. Note that B should be an array obtained after shuffling the elements of A.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{5}$
$The frequency of each integer in the array A will be at most 2.$

------ Subtasks ------ 

Subtask #1 (30 points): all elements in the array A are unique

Subtask #2 (30 points): 5 ≤ N ≤ 10^{5}

Subtask #3 (40 points): original constraints

----- Sample Input 1 ------ 
3

2

1 2

3

1 2 1

4

2 6 5 2
----- Sample Output 1 ------ 
2

2 1

2

2 1 1

4

6 2 2 5

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	a = []
	b = []
	for i in range(n):
		a.append([li[i], i])
		b.append(li[i])
	a.sort()
	b.sort(reverse=True)
	flag = False
	for i in range(n):
		if b[i] == a[i][0]:
			if flag == False:
				(b[i], b[0]) = (b[0], b[i])
				flag = True
			else:
				(b[i], b[n - 1]) = (b[n - 1], b[i])
	ct = 0
	co = [0] * n
	for i in range(n):
		if b[i] != a[i][0]:
			ct += 1
		co[a[i][1]] = b[i]
	print(ct)
	print(*co)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	b = []
	for j in range(n):
		a.append([l[j], j])
		b.append(l[j])
	a.sort()
	b.sort(reverse=True)
	f = False
	for k in range(n):
		if b[k] == a[k][0]:
			if f == False:
				(b[k], b[0]) = (b[0], b[k])
				f = True
			else:
				(b[k], b[n - 1]) = (b[n - 1], b[k])
	c = 0
	s = [0] * n
	for z in range(n):
		if b[z] != a[z][0]:
			c += 1
		s[a[z][1]] = b[z]
	print(c)
	print(*s)


tc = int(input())
for _ in range(tc):
	n = int(input())
	lst = list(map(int, input().split()))
	A = []
	B = []
	for i in range(n):
		A.append([lst[i], i])
		B.append(lst[i])
	A.sort()
	B.sort(reverse=True)
	flag = False
	for i in range(n):
		if B[i] == A[i][0]:
			if flag == False:
				(B[i], B[0]) = (B[0], B[i])
				flag = True
			else:
				(B[i], B[n - 1]) = (B[n - 1], B[i])
	cnt = 0
	con = [0] * n
	for i in range(n):
		if B[i] != A[i][0]:
			cnt += 1
		con[A[i][1]] = B[i]
	print(cnt)
	print(*con)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	b = [0] * n
	for i in range(n):
		d[a[i]] = d.get(a[i], []) + [i]
	if n == 2:
		b[0] = a[1]
		b[1] = a[0]
	elif n == 3:
		p = a[0]
		b[0] = a[1]
		b[1] = a[2]
		b[2] = p
	elif n == 1:
		b[0] = a[0]
		k = 1
	else:
		d1 = {}
		d2 = {}
		for i in d:
			if len(d[i]) == 1:
				d1[i] = d[i]
			else:
				d2[i] = d[i]
		ld1 = list(d1.keys())
		ld2 = list(d2.keys())
		if len(d1) > 1 and len(d2) > 1:
			p = d1[ld1[0]][0]
			for i in range(1, len(ld1)):
				d1[ld1[i - 1]][0] = d1[ld1[i]][0]
			d1[ld1[i]][0] = p
			p = d2[ld2[0]]
			for i in range(1, len(ld2)):
				d2[ld2[i - 1]] = d2[ld2[i]]
			d2[ld2[i]] = p
		elif len(d1) == 0:
			p = d2[ld2[0]]
			for i in range(1, len(ld2)):
				d2[ld2[i - 1]] = d2[ld2[i]]
			d2[ld2[i]] = p
		elif len(d2) == 0:
			p = d1[ld1[0]][0]
			for i in range(1, len(ld1)):
				d1[ld1[i - 1]][0] = d1[ld1[i]][0]
			d1[ld1[i]][0] = p
		elif len(d1) == 1:
			p = d2[ld2[0]]
			for i in range(1, len(ld2)):
				d2[ld2[i - 1]] = d2[ld2[i]]
			d2[ld2[i]] = p
			p = d1[ld1[0]][0]
			d1[ld1[0]][0] = d2[ld2[0]][0]
			d2[ld2[0]][0] = p
		elif len(d2) == 1:
			p = d1[ld1[0]][0]
			for i in range(1, len(ld1)):
				d1[ld1[i - 1]][0] = d1[ld1[i]][0]
			d1[ld1[i]][0] = p
			(x, y) = (d2[ld2[0]][0], d2[ld2[0]][1])
			d2[ld2[0]][0] = d1[ld1[0]][0]
			d2[ld2[0]][1] = d1[ld1[1]][0]
			d1[ld1[1]][0] = x
			d1[ld1[0]][0] = y
		for i in d1:
			b[d1[i][0]] = i
		for i in d2:
			b[d2[i][0]] = i
			b[d2[i][1]] = i
	c = 0
	for i in range(n):
		if b[i] != a[i]:
			c += 1
	print(c)
	print(*b)


def swap(b, i, x, n):
	if a[i] != b[i + x]:
		temp = b[i]
		b[i] = b[i + x]
		b[i + x] = temp
	elif x < n - 2:
		x += 1
		swap(b, i, x, n)
	return b
for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = a[::-1]
	ct = 0
	if n > 2:
		for i in range(n - 1):
			x = 0
			if a[i] == b[i + x]:
				if x < n - 2:
					x += 1
					swap(b, i, x, n)
				else:
					break
		if a[n - 1] == b[n - 1]:
			if a[n - 1] != b[0]:
				temp = b[n - 1]
				b[n - 1] = b[0]
				b[0] = temp
			elif a[n - 1] != b[n // 2]:
				temp = b[n // 2]
				b[n // 2] = b[n - 1]
				b[n - 1] = temp
		if a[0] == b[0]:
			if a[n - 1] != b[1]:
				temp = b[0]
				b[0] = b[1]
				b[0] = temp
			elif a[0] != b[n // 2]:
				temp = b[n // 2]
				b[n // 2] = b[0]
				b[0] = temp
	if n >= 4:
		ct = n
	else:
		for i in range(n):
			if a[i] != b[i]:
				ct += 1
	print(ct)
	print(' '.join((str(x) for x in b)))


from itertools import permutations
from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	h = 0
	b = a.copy()
	if n <= 4:
		b = a.copy()
		for p in list(permutations(a)):
			temph = 0
			for i in range(n):
				if a[i] != p[i]:
					temph += 1
			if temph > h:
				h = temph
				b = p
	else:
		h = n
		while True:
			for i in range(n):
				if a[i] == b[i]:
					b.append(b.pop(0))
					break
			else:
				break
	print(h)
	print(*b)


from itertools import permutations

def Shift(A):
	A.append(A.pop(0))
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	h = 0
	b = a.copy()
	if n <= 4:
		b = a.copy()
		for p in list(permutations(a)):
			temph = 0
			for i in range(n):
				if a[i] != p[i]:
					temph += 1
			if temph > h:
				h = temph
				b = p
	else:
		h = n
		while True:
			for i in range(n):
				if a[i] == b[i]:
					Shift(b)
					break
			else:
				break
	print(h)
	print(*b)


def ip():
	return int(input())

def ipp():
	return map(int, input().split())

def sar():
	return list(ipp())

def pars(a):
	print(' '.join(list(map(str, a))))

def parl(a):
	print('\r'.join(list(map(str, a))))

def ham(a, b):
	s = 0
	for i in range(len(a)):
		if a[i] != b[i]:
			s += 1
	return s

def ans(a, n):
	b = [0] * len(a)
	for i in range(len(a)):
		for j in range(len(a)):
			b[j] = a[(i + j) % len(a)]
		if ham(a, b) == n:
			break
	print(n)
	pars(b)
T = 1
T = int(input().strip())
for _ in range(T):
	n = ip()
	a = []
	a = sar()
	if n == 2 and a[0] == a[1] or n == 1:
		ans(a, 0)
	elif n == 3 and (a[0] == a[1] or a[1] == a[2] or a[0] == a[2]):
		ans(a, 2)
	else:
		ans(a, n)


t = int(input())
for x in range(t):
	n = int(input())
	arrA = [int(i) for i in input().split()]
	nc = 0
	mydb = {}
	for i in range(n):
		if arrA[i] in mydb:
			mydb[arrA[i]][1] += 1
			mydb[arrA[i]][2] = i
			nc += 1
		else:
			mydb[arrA[i]] = [i, 1, -1]
	ci = 0
	si = nc
	ns = n - 2 * nc
	barray = [0] * (n + 2)
	index = [-1] * n
	adj = 1
	if nc == 1:
		adj = 2
	else:
		adj = 1
	for num in arrA:
		tmplist = mydb[num]
		if tmplist[1] == 1:
			barray[si + adj] = num
			index[si] = tmplist[0]
			si += 1
		elif tmplist[1] == 2:
			barray[ci + adj] = num
			index[ci] = tmplist[0]
			barray[ci + nc + ns + adj] = num
			index[ci + nc + ns] = tmplist[2]
			ci += 1
			tmplist[1] = 0
	if adj == 1:
		barray[0] = barray[n]
	elif adj == 2:
		barray[0] = barray[n]
		barray[1] = barray[n + 1]
	newB = [0] * n
	for i in range(n):
		newB[index[i]] = barray[i]
	if n == 3 and nc == 1:
		print(2)
	elif n == 1 or (n == 2 and nc == 1):
		print(0)
	else:
		print(n)
	for i in range(n):
		print(newB[i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	l1 += l[n // 2:]
	l1 += l[:n // 2]
	c = 0
	for i in range(len(l)):
		if l[i] != l1[i]:
			c += 1
	print(c)
	for i in l1:
		print(i, end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split(' ')))
	b = a[:]
	distance = 0
	for j in range(n):
		if a[j] != b[j]:
			continue
		for k in range(n):
			if a[j] != b[k] and a[k] != b[j]:
				(b[j], b[k]) = (b[k], b[j])
				break
	for j in range(n):
		if a[j] != b[j]:
			distance += 1
	print(distance)
	print(' '.join(map(str, b)))


def ham(A, B, n, c):
	dist = 0
	for i in range(n):
		if A[i] != B[i]:
			dist = dist + 1
	print(dist)

def shuffle(A, n):
	B = [None] * n
	T = list()
	T = sorted(A)
	flag = 0
	for i in range(n):
		for j in range(i, n):
			if A[i] != T[j]:
				if i == j:
					break
				elif A[j] != T[i]:
					temp = T[j]
					T[j] = T[i]
					T[i] = temp
					flag = 1
					break
	conflict = list()
	for i in range(n):
		if A[i] == T[i]:
			conflict.append(i)
	count = 0
	for con in range(len(conflict)):
		c = conflict[con]
		for i in range(n):
			if T[i] != T[c] and A[i] != T[c] and (A[c] != T[i]):
				temp = T[c]
				T[c] = T[i]
				T[i] = temp
				count = count + 1
				break
	ham(A, T, n, count)
	for i in range(n):
		print(T[i], end=' ')
	print()
Case = int(input())
for i in range(Case):
	n = int(input())
	numbers = list(map(int, input().split()))
	if n != 1:
		shuffle(numbers, n)
	else:
		print(0)
		print(numbers[0])


def dist(a, ans):
	c = 0
	for i in range(0, n):
		if a[i] == ans[i]:
			c += 1
	return c
t = int(input())
for iteration in range(0, t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	ans = [i for i in a]
	c = dist(a, ans)
	for i in range(0, n):
		if a[i] == ans[i]:
			for j in range(0, n):
				if i != j and a[i] != ans[j] and (a[j] != ans[i]):
					(ans[i], ans[j]) = (ans[j], ans[i])
	c = dist(a, ans)
	print(n - c)
	print(' '.join(list(map(lambda x: str(x), ans))))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(a)
	for i in range(n):
		if a[i] != b[i]:
			continue
		for j in range(n):
			if i == j:
				continue
			if a[i] != b[j] and a[j] != b[i]:
				(b[i], b[j]) = (b[j], b[i])
	h = 0
	for i in range(n):
		if a[i] != b[i]:
			h += 1
	print(h)
	for each in b:
		print(each, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if n == 1 or (n == 2 and a[0] == a[1]):
		print(0)
		print(' '.join([str(i) for i in a]))
		continue
	elif n == 3 and (a[0] == a[1] or a[0] == a[2] or a[1] == a[2]):
		print(2)
		if a[0] == a[1]:
			(a[1], a[2]) = (a[2], a[1])
		elif a[1] == a[2]:
			(a[0], a[2]) = (a[2], a[0])
		elif a[0] == a[2]:
			(a[0], a[1]) = (a[1], a[0])
		print(' '.join([str(i) for i in a]))
		continue
	else:
		print(n)
		if n == 2:
			(a[0], a[1]) = (a[1], a[0])
			print(' '.join([str(i) for i in a]))
			continue
	latencies = set()
	index = {}
	for i in range(len(a)):
		if a[i] in index.keys():
			latencies.add(i - index[a[i]])
			latencies.add(n - (i - index[a[i]]))
		else:
			index[a[i]] = i
	rot = 1
	while rot <= len(a):
		if rot not in latencies:
			break
		rot += 1
	a = a[rot:] + a[:rot]
	print(' '.join([str(i) for i in a]))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	new_l = l[:]
	for i in range(n - 1):
		(l[i], l[i + 1]) = (l[i + 1], l[i])
	hd = n
	for i in range(n):
		if l[i] == new_l[i]:
			for j in range(n):
				if l[i] != l[j] and l[i] != new_l[j]:
					(l[i], l[j]) = (l[j], l[i])
					break
			else:
				hd -= 1
	print(hd)
	print(*l)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		a = str(input())
		print(0)
		print(a)
	else:
		a = [s for s in input().split()]
		p = set(a)
		if len(p) != len(a):
			if n == 3:
				b = [a[-1]] + a[:-1]
				print(2)
				print(' '.join(b))
			elif n != 2:
				b = [a[-1]] + a[:-1]
				d = len(b)
				for k in range(d):
					if b[k] == a[k]:
						for m in range(d):
							if b[m] != b[k] and b[k] != a[m]:
								temp = b[k]
								b[k] = b[m]
								b[m] = temp
								break
				print(n)
				print(' '.join(b))
			else:
				print(0)
				print(' '.join(a))
		else:
			b = [a[-1]] + a[:-1]
			print(n)
			print(' '.join(b))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	z = [0] * n
	if n == 1:
		print(0)
		print(a[0])
	elif n == 2:
		if a[0] == a[1]:
			print(0)
			print(a[0], a[1])
		else:
			print(2)
			print(a[1], a[0])
	elif n == 3:
		if a[0] == a[1]:
			print(2)
			print(a[2], a[0], a[1])
		elif a[0] == a[2]:
			print(2)
			print(a[1], a[0], a[2])
		elif a[1] == a[2]:
			print(2)
			print(a[1], a[0], a[2])
		else:
			print(3)
			print(a[2], a[0], a[1])
	else:
		r = n % 4
		tt = n // 4
		if r == 3:
			if a[n - 3] == a[n - 2]:
				z[n - 1] = a[n - 3]
				z[n - 3] = a[n - 1]
			elif a[n - 3] == a[n - 1]:
				z[n - 3] = a[n - 2]
				z[n - 2] = a[n - 3]
			elif a[n - 1] == a[n - 2]:
				z[n - 2] = a[n - 3]
				z[n - 3] = a[n - 2]
			else:
				z[n - 3] = a[n - 1]
				z[n - 2] = a[n - 3]
				z[n - 1] = a[n - 2]
		for i in range(0, tt * 4 - 4 + 1, 4):
			if a[i + 2] == a[i + 3] or a[i] == a[i + 1]:
				z[i] = a[i + 3]
				z[i + 3] = a[i]
				z[i + 1] = a[i + 2]
				z[i + 2] = a[i + 1]
			elif a[i] == a[i + 2] or a[i] == a[i + 3] or a[i + 1] == a[i + 3] or (a[i + 1] == a[i + 2]):
				z[i] = a[i + 1]
				z[i + 1] = a[i]
				z[i + 2] = a[i + 3]
				z[i + 3] = a[i + 2]
			else:
				z[i] = a[i + 1]
				z[i + 1] = a[i]
				z[i + 2] = a[i + 3]
				z[i + 3] = a[i + 2]
		if z[n - 1] == 0 and z[n - 2] == 0:
			rmt = a[n - 2]
			smt = a[n - 1]
			z[n - 2] = z[0]
			z[n - 1] = z[1]
			z[0] = rmt
			z[1] = smt
		elif z[n - 1] == 0:
			for i in range(n):
				if a[n - 1] != z[i] and a[i] != a[n - 1]:
					z[n - 1] = z[i]
					z[i] = a[n - 1]
					break
		elif z[n - 2] == 0:
			for i in range(n):
				if a[n - 2] != z[i] and a[i] != a[n - 2]:
					z[n - 2] = z[i]
					z[i] = a[n - 2]
					break
		print(n)
		for i in range(n):
			print(z[i], end=' ')
		print()
	t = t - 1


t = int(input())
while t > 0:
	n = int(input())
	c = [0] * n
	b = list(map(int, input().split()))
	if n == 1:
		print(0)
		print(b[0])
	if n == 2:
		if b[0] == b[1]:
			print(0)
			print(b[0], b[1])
		else:
			print(2)
			print(b[1], b[0])
	if n == 3:
		if b[0] == b[1] or b[1] == b[2] or b[2] == b[0]:
			print(2)
			if b[0] == b[1]:
				print(b[2], b[0], b[1])
			elif b[1] == b[2]:
				print(b[1], b[0], b[2])
			elif b[0] == b[2]:
				print(b[1], b[0], b[2])
		else:
			print(3)
			print(b[2], b[0], b[1])
	if n >= 4:
		x = []
		print(n)
		for i in range(n):
			for j in range(i - 2, n):
				if c[j] == 0 and b[j] != b[i] and (j != i):
					if j >= 0:
						c[j] = b[i]
						break
		if c[n - 1] == 0:
			if c[n - 2] == 0:
				c[n - 1] = c[0]
				c[n - 2] = c[1]
				c[0] = b[n - 1]
				c[1] = b[n - 2]
			else:
				for i in range(n):
					if b[n - 1] != b[i] and c[i] != b[n - 1]:
						c[n - 1] = c[i]
						c[i] = b[n - 1]
						break
		if c[n - 1] != 0 and c[n - 2] == 0:
			for i in range(n):
				if b[n - 2] != b[i] and c[i] != b[n - 2]:
					c[n - 2] = c[i]
					c[i] = b[n - 2]
					break
		print(' '.join(map(str, c)))
	t = t - 1


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	if n > 3:
		print(n)
		j = 0
		v = l[0:n]
		z = [0 for i in range(n)]
		while j < n:
			if z[j] == 1:
				j += 1
				continue
			temp = l[j]
			k = j + 1
			while k < n and (z[k] != 0 or v[j] == v[k]):
				k += 1
			if k != n:
				(v[j], v[k]) = (v[k], v[j])
				z[j] = 1
				z[k] = 1
			j += 1
		j = 0
		while j < n:
			if z[j] == 0:
				for i in range(n):
					if v[i] != v[j] and l[i] != l[j]:
						(v[i], v[j]) = (v[j], v[i])
						z[j] = 1
						break
			j += 1
		for i in v:
			print(i, end=' ')
	elif n == 1:
		print(0)
		print(l[0])
	elif n == 2:
		if l.count(l[0]) > 1:
			print(0)
			print(l[0], l[1])
		else:
			print(2)
			print(l[1], l[0])
	else:
		x = l.count(l[0])
		y = l.count(l[1])
		z = l.count(l[2])
		if x > 1:
			print(2)
			print(l[0], l[2], l[1])
		elif y > 1:
			print(2)
			print(l[2], l[1], l[0])
		else:
			print(3)
			print(l[2], l[0], l[1])
	t -= 1


for _ in range(int(input())):
	m = int(input())
	array = list(map(int, input().split()))
	array2 = list(array)
	array3 = []
	if m == 1:
		print(0)
		print(*array)
	else:
		for i in range(m):
			array[i] = str(array2[i - 1])
			if str(array[i]) == str(array2[i]):
				array3.append(i)
		array4 = list(array)
		if len(array3) <= 0:
			print(m)
			print(*array)
		elif len(array3) == 1:
			if m == 3:
				print(2)
				print(*array)
			else:
				(array[array3[0]], array[array3[0] - 2]) = (array[array3[0] - 2], array[array3[0]])
				print(m)
				print(*array)
		elif m == 2:
			print(0)
			print(*array2)
		else:
			for i in range(len(array3)):
				array[array3[i]] = int(array4[array3[i - 1]])
			print(m)
			print(*array)


for _ in range(int(input())):
	no = input()
	no = int(no)
	arr = map(int, input().split())
	arr = list(arr)
	st = 0
	if no == 1 and st == 0:
		print(no - 1)
		ansarr = []
		ansarr.append(arr[0])
		print(*ansarr)
		st = 1
	elif no == 2 and st == 0:
		if arr[1] == arr[0]:
			print(no - 2)
			ansarr = []
			ansarr.append(arr[0])
			ansarr.append(arr[1])
			print(*ansarr)
			st = 1
		else:
			print(no)
			ansarr = []
			ansarr.append(arr[1])
			ansarr.append(arr[0])
			print(*ansarr)
			st = 1
	elif no == 3 and st == 0:
		if arr[0] == arr[2] or arr[0] == arr[1] or arr[2] == arr[1]:
			print('2')
			ansarr = []
			ansarr.append(arr[2])
			ansarr.append(arr[0])
			ansarr.append(arr[1])
			print(*ansarr)
			st = 1
		else:
			print('3')
			ansarr = []
			ansarr.append(arr[1])
			ansarr.append(arr[2])
			ansarr.append(arr[0])
			print(*ansarr)
			st = 1
	elif no == 4 and st == 0:
		print('4')
		ansarr = []
		for i in range(no):
			ansarr.append(-5)
		if len(set(arr)) == no:
			ansarr = arr[::-1]
			print(*ansarr)
			st = 1
		else:
			ansarr = []
			for i in range(no):
				ansarr.append(-5)
			if arr[2] == arr[3]:
				(ansarr[0], ansarr[1], ansarr[2], ansarr[3]) = (arr[3], arr[2], arr[1], arr[0])
				print(*ansarr)
				st = 1
			else:
				temp2 = []
				for i in range(4):
					temp2.append(arr[i])
				poin = 0
				element = temp2[poin]
				while poin != no:
					element = temp2[poin]
					for j in range(no):
						if arr[j] != element and ansarr[j] == -5:
							ansarr[j] = element
							poin += 1
							break
				print(*ansarr)
				st = 1
	else:
		print(no)
		ansarr = []
		for i in range(no):
			ansarr.append(-5)
		rep = []
		temp = arr[no - 1]
		for j in range(no - 1):
			ansarr[j + 1] = arr[j]
			if arr[j] == arr[j + 1]:
				rep.append(j + 1)
		if arr[0] == arr[no - 1]:
			rep.append(0)
		ansarr[0] = temp
		repc = len(rep)
		if repc > 0:
			if repc == 1:
				for x in range(no):
					if rep[0] != x:
						temp = x
						break
				if rep[0] == no - 1:
					temp += 1
				(ansarr[temp], ansarr[rep[0]]) = (ansarr[rep[0]], ansarr[temp])
			elif len(rep) == 2:
				(ansarr[rep[1]], ansarr[rep[0]]) = (ansarr[rep[0]], ansarr[rep[1]])
			else:
				for i in range(len(rep) - 1):
					h2 = rep[i + 1]
					h1 = rep[i]
					(ansarr[h1], ansarr[h2]) = (ansarr[h2], ansarr[h1])
		print(*ansarr)


MAX = 100001
t = int(input())
for z in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	c = [0] * MAX
	for i in a:
		c[i] += 1
	if n == 1:
		print(0)
		print(a[0])
		continue
	if n == 2:
		if a[0] == a[1]:
			print(0)
			print(a[0], a[0])
		else:
			print(2)
			print(a[1], a[0])
		continue
	if n == 3:
		if a[0] == a[1]:
			print(2)
			print(a[2], a[1], a[0])
		elif a[0] == a[2]:
			print(2)
			print(a[0], a[2], a[1])
		elif a[1] == a[2]:
			print(2)
			print(a[1], a[0], a[2])
		else:
			print(3)
			print(a[1], a[2], a[0])
		continue
	print(n)
	x = []
	y = []
	for i in range(MAX):
		if c[i] == 1:
			x.append(i)
		elif c[i] == 2:
			y.append(i)
	d = {}
	if len(x) == 0:
		d[y[0]] = y[len(y) - 1]
		for i in range(1, len(y)):
			d[y[i]] = y[i - 1]
		for i in range(n):
			print(d[a[i]], end=' ')
		print()
	elif len(y) == 0:
		d[x[0]] = x[len(x) - 1]
		for i in range(1, len(x)):
			d[x[i]] = x[i - 1]
		for i in range(n):
			print(d[a[i]], end=' ')
		print()
	elif len(y) == 1:
		for i in range(2, len(x)):
			d[x[i]] = x[i - 2]
		d[x[0]] = y[0]
		d[x[1]] = y[0]
		flag = 0
		for i in range(n):
			if c[a[i]] == 1:
				print(d[a[i]], end=' ')
			elif flag == 0:
				print(x[len(x) - 1], end=' ')
				flag = 1
			else:
				print(x[len(x) - 2], end=' ')
		print()
	elif len(x) == 1:
		for i in range(1, len(y)):
			d[y[i]] = y[i - 1]
		flag = 0
		for i in range(n):
			if c[a[i]] == 1:
				print(y[len(y) - 1], end=' ')
			elif a[i] == y[0]:
				if flag == 0:
					print(y[len(y) - 1], end=' ')
					flag = 1
				else:
					print(x[0], end=' ')
			else:
				print(d[a[i]], end=' ')
		print()
	else:
		d[x[0]] = x[len(x) - 1]
		for i in range(1, len(x)):
			d[x[i]] = x[i - 1]
		d[y[0]] = y[len(y) - 1]
		for i in range(1, len(y)):
			d[y[i]] = y[i - 1]
		for i in range(n):
			print(d[a[i]], end=' ')
		print()


test = int(input())
for _ in range(test):
	n = int(input())
	l = list(map(int, input().split()))
	nl = l[:]
	hammed = [0 for i in range(n)]
	cnt = 0
	for i in range(n - 1):
		if l[i] == nl[i]:
			(nl[i], nl[i + 1]) = (nl[i + 1], nl[i])
			if l[i] != nl[i]:
				cnt += 1
				hammed[i] = 1
			elif i + 2 < n:
				(nl[i], nl[i + 2]) = (nl[i + 2], nl[i])
				cnt += 1
				hammed[i] = 1
		else:
			cnt += 1
			hammed[i] = 1
	if l[-1] != nl[-1]:
		cnt += 1
		hammed[-1] = 1
	else:
		try:
			temp = hammed.index(1)
			if l[temp] != nl[-1] and nl[temp] != l[-1]:
				(nl[temp], nl[-1]) = (nl[-1], nl[temp])
				cnt += 1
			else:
				for i in range(temp + 1, n):
					if hammed[i] == 1 and nl[-1] != l[i] and (nl[i] != l[-1]):
						(nl[i], nl[-1]) = (nl[-1], nl[i])
						cnt += 1
						break
		except:
			pass
	for i in range(n - 1):
		if hammed[i] == 0:
			try:
				temp = hammed.index(1)
				if l[temp] != nl[i] and nl[temp] != l[i]:
					(nl[temp], nl[i]) = (nl[i], nl[temp])
					cnt += 1
				else:
					for j in range(temp + 1, n):
						if hammed[j] == 1 and nl[i] != l[j] and (nl[j] != l[i]):
							(nl[j], nl[i]) = (nl[i], nl[j])
							cnt += 1
							break
			except:
				pass
	print(cnt)
	print(*nl)


for _ in range(int(input())):
	ans = []
	n = int(input())
	l = [int(x) for x in input().rstrip().split()]
	if n == 1:
		print(0)
		print(l[0])
		continue
	elif n == 2:
		if l[0] == l[1]:
			print(0)
			ans = l
		else:
			print(2)
			ans = [l[1], l[0]]
		for i in range(n):
			print(ans[i], end=' ')
		print()
		continue
	elif n == 3:
		if l[0] != l[1] and l[1] != l[2] and (l[0] != l[2]):
			ans = [l[1], l[2], l[0]]
			print(3)
		else:
			print(2)
			if l[2] == l[0]:
				ans = [l[1], l[0], l[2]]
			else:
				ans = [l[2], l[0], l[1]]
		for i in range(n):
			print(ans[i], end=' ')
		print()
		continue
	else:
		print(n)
		ans = [-999] * n
		rem = n % 4
		nn = n - rem
		for i in range(0, nn, 4):
			a = l[i]
			b = l[i + 1]
			c = l[i + 2]
			d = l[i + 3]
			if a == c or b == d:
				ans[i] = b
				ans[i + 1] = a
				ans[i + 2] = d
				ans[i + 3] = c
				continue
			else:
				ans[i] = c
				ans[i + 1] = d
				ans[i + 2] = a
				ans[i + 3] = b
				continue
		if rem == 1:
			for jij in range(0, 4):
				if l[jij] != l[-1] and ans[jij] != l[-1]:
					ans[-1] = ans[jij]
					ans[jij] = l[-1]
					break
		elif rem == 2:
			lasta = l[-2]
			lastb = l[-1]
			if lasta == lastb:
				ans[-2] = ans[0]
				ans[-1] = ans[1]
				ans[0] = lasta
				ans[1] = lastb
			else:
				ans[-1] = l[-2]
				ans[-2] = l[-1]
		elif rem == 3:
			a = l[-3]
			b = l[-2]
			c = l[-1]
			if a == b:
				ans[-3] = l[-1]
				ans[-1] = l[-3]
				loc = -2
				for jij in range(0, 4):
					if l[jij] != l[loc] and ans[jij] != l[loc]:
						ans[loc] = ans[jij]
						ans[jij] = l[loc]
						break
			elif b == c:
				ans[-3] = l[-2]
				ans[-2] = l[-3]
				loc = -1
				for jij in range(0, 5):
					if l[jij] != l[loc] and ans[jij] != l[loc]:
						ans[loc] = ans[jij]
						ans[jij] = l[loc]
						break
			elif a == c:
				ans[-3] = l[-2]
				ans[-2] = l[-3]
				loc = -1
				for jij in range(0, 5):
					if l[jij] != l[loc] and ans[jij] != l[loc]:
						ans[loc] = ans[jij]
						ans[jij] = l[loc]
						break
			else:
				ans[-1] = a
				ans[-2] = c
				ans[-3] = b
		for i in range(2):
			if l[i] == ans[i]:
				(ans[i + 2], ans[i]) = (ans[i], ans[i + 2])
		for i in range(2, n):
			if l[i] == ans[i]:
				(ans[i - 2], ans[i]) = (ans[i], ans[i - 2])
		for i in range(n):
			print(ans[i], end=' ')
		print()


for sadadsads in range(int(input())):
	n = int(input())
	a = list(map(lambda x: int(x), input().split()))
	b = [i for i in a]
	c = []
	d = {}
	for i in a:
		d[i] = i
	if len(d) == n:
		(a[n // 2], a[-1]) = (a[-1], a[n // 2])
		a = a[::-1]
	else:
		i = 0
		while i < len(a) - 3:
			if a[i + 1] == a[i]:
				(a[i + 2], a[i]) = (a[i], a[i + 2])
				(a[i + 3], a[i + 2]) = (a[i + 2], a[i + 3])
			else:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
			i += 2
		if len(a) > 1:
			if len(a) == 2:
				a = a[::-1]
			else:
				if a[-1] == a[-2]:
					(a[-2], a[-3]) = (a[-3], a[-2])
				elif a[-2] == a[-3]:
					(a[-1], a[-3]) = (a[-3], a[-1])
				for i in range(len(a)):
					if a[i] != a[-3] and a[-3] != b[i]:
						(a[i], a[-3]) = (a[-3], a[i])
	dist = 0
	if n > 3 and n < 500:
		for i in range(n):
			if b[i] != a[i]:
				dist += 1
	if n < 500 and dist != n:
		a = [i for i in b]
		b = sorted(a)
		c = []
		for i in range(len(a)):
			if b[0] == a[i]:
				c.append(b[-1])
				del b[-1]
			else:
				c.append(b[0])
				del b[0]
		if len(a) == 1:
			print(0)
		elif len(a) == 2:
			if a[0] == a[1]:
				print(0)
			else:
				print(2)
		elif len(a) == 3:
			if a[0] == a[1] or a[1] == a[2] or a[0] == a[2]:
				print(2)
			else:
				print(3)
		else:
			print(len(a))
		for i in c:
			print(i, end=' ')
		print()
	else:
		if len(a) == 1:
			print(0)
		elif len(a) == 2:
			if a[0] == a[1]:
				print(0)
			else:
				print(2)
		elif len(a) == 3:
			if a[0] == a[1] or a[1] == a[2] or a[0] == a[2]:
				print(2)
			else:
				print(3)
		else:
			print(len(a))
		for i in a:
			print(i, end=' ')
		print()


T = int(input())
for P in range(T):
	n = int(input())
	x = input().split()
	y = list(reversed(x))
	z = y.copy()
	for j in range(n):
		if x[j] == y[j]:
			for i in range(n):
				if y[i] != y[j]:
					if x[i] != y[j]:
						b = y[i]
						y[i] = y[j]
						y[j] = b
						break
	m = 0
	for i in range(n):
		if x[i] != y[i]:
			m += 1
	print(m)
	N = ''
	for i in y:
		N += str(i) + ' '
	N = N[0:-1]
	print(N)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = 'ncorr'
	if len(a) == 1:
		print(0)
		print(a[0])
		continue
	if n == len(set(a)):
		print(n)
		print(' '.join([str(a[n - 1])] + [str(a[i]) for i in range(n - 1)]))
		continue
	if n == 2:
		print(0)
		print(a[0], a[0])
		continue
	if n == 3:
		print(2)
		print(a[1], a[2], a[0])
		continue
	ans = [a[n - 2], a[n - 1]] + [a[i] for i in range(n - 2)]
	while f == 'ncorr':
		f = 'corr'
		if ans[n - 1] == a[n - 1]:
			(ans[0], ans[n - 1]) = (ans[n - 1], ans[0])
			f = 'ncorr'
		for i in range(n - 1):
			if a[i] == ans[i]:
				(ans[i], ans[i + 1]) = (ans[i + 1], ans[i])
				f = 'ncorr'
	ans = list(map(str, ans))
	print(n)
	print(' '.join(ans))


t = int(input())
while t:
	n = int(input())
	ct = 0
	has = []
	has1 = []
	has2 = []
	has3 = []
	b = []
	a = list(map(int, input().split()))
	for i in range(0, n):
		b.append(a[i])
	for i in range(0, 100010):
		has.append(0)
		has3.append(0)
	for i in range(0, n):
		has[a[i]] += 1
	s = set(a)
	sz = len(s)
	s = list(s)
	for i in range(0, sz):
		if has[s[i]] == 2:
			has2.append(s[i])
		else:
			has1.append(s[i])
	s1 = len(has1)
	s2 = len(has2)
	for i in range(0, s2 - 1, 2):
		has3[has2[i]] = has2[i + 1]
		has3[has2[i + 1]] = has2[i]
	for i in range(0, s1 - 1, 2):
		has3[has1[i]] = has1[i + 1]
		has3[has1[i + 1]] = has1[i]
	for i in range(0, n):
		if has3[b[i]] != 0:
			b[i] = has3[b[i]]
	for i in range(0, n, 1):
		if a[i] == b[i]:
			if i + 1 < n and b[i] != a[i + 1]:
				(b[i], b[i + 1]) = (b[i + 1], b[i])
			elif i - 1 >= 0 and b[i] != a[i - 1]:
				(b[i], b[i - 1]) = (b[i - 1], b[i])
			elif i == 0 or i == n - 1:
				(b[0], b[n - 1]) = (b[n - 1], b[0])
	for i in range(0, n):
		if a[i] != b[i]:
			ct += 1
	print(ct)
	print(*b)
	t -= 1


while True:
	try:
		t = int(input())
	except EOFError:
		break
	break
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = set(a)
	hd = 0
	b = []
	if n == len(c):
		if len(a) % 2 == 0:
			b = a[::-1]
			hd = len(b)
		elif len(a) > 1 and len(a) % 2 != 0:
			b = a[::-1]
			(b[int(n / 2)], b[int(n / 2) + 1]) = (b[int(n / 2) + 1], b[int(n / 2)])
			hd = len(b)
		elif len(a) == 1:
			b = a
			hd = 0
		print(hd)
		print(' '.join((str(x) for x in b)))
	else:
		hd = len(a)
		b = [x for x in a]
		for i in range(n - 2):
			if a[i] != a[i + 2]:
				(a[i], a[i + 2]) = (a[i + 2], a[i])
			elif a[i] != a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
		for i in range(n - 1):
			if a[i] == b[i]:
				if a[i + 1] != b[i]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
				elif a[i - 1] != b[i] and i != 0:
					(a[i], a[i - 1]) = (a[i - 1], a[i])
		if a[-1] == b[-1]:
			if a[-2] == b[-1] and len(a) > 3:
				(a[-3], a[-1]) = (a[-1], a[-3])
			if a[-2] != b[-1]:
				(a[-2], a[-1]) = (a[-1], a[-2])
		if a[0] == b[0] and a[1] == b[0] and (len(a) > 3):
			(a[0], a[2]) = (a[2], a[0])
		for i in range(n):
			if a[i] == b[i]:
				hd -= 1
		print(hd)
		print(' '.join((str(x) for x in a)))


def swap(a, ind):
	(a[ind], a[ind - 2]) = (a[ind - 2], a[ind])
	(a[ind - 1], a[ind - 3]) = (a[ind - 3], a[ind - 1])
t = int(input())
for _ in range(t):
	hd = 0
	n = int(input())
	ar = list(map(int, input().split()))
	i = n - 1
	if n == 1:
		print(0)
		print(*ar)
	elif n == 2:
		if ar[0] == ar[1]:
			print(0)
			print(*ar)
		else:
			print(2)
			print(ar[1], ar[0])
	elif len(ar) == len(set(ar)):
		print(n)
		print(*ar[1:n], ar[0])
	elif n == 3:
		if ar[2] == ar[1] or ar[0] == ar[2]:
			(ar[0], ar[1]) = (ar[1], ar[0])
		elif ar[1] == ar[0]:
			(ar[1], ar[2]) = (ar[2], ar[1])
		print(2)
		print(*ar)
	else:
		tmp = ar[0]
		while i > 0:
			if ar[i] == ar[i - 1]:
				if i > 2:
					swap(ar, i)
					i = i - 4
					hd = hd + 4
				elif i == 2:
					(ar[2], ar[n - 1]) = (ar[n - 1], ar[2])
					(ar[1], ar[n - 2]) = (ar[n - 2], ar[1])
					(ar[0], ar[n - 3]) = (ar[n - 3], ar[0])
					hd = hd + 3
					i = 0
				elif i == 1:
					(ar[1], ar[n - 1]) = (ar[n - 1], ar[1])
					(ar[0], ar[n - 2]) = (ar[n - 2], ar[0])
					hd = hd + 2
					i = 0
			elif ar[i] != ar[i - 1]:
				(ar[i], ar[i - 1]) = (ar[i - 1], ar[i])
				hd = hd + 2
				i = i - 2
		if ar[0] == tmp:
			(ar[0], ar[n - 1]) = (ar[n - 1], ar[0])
			hd += 1
		print(n)
		print(*ar)


t = int(input())
l1 = [0] * 100000
l2 = [0] * 100000
c = 0
for i in range(0, t):
	n = int(input())
	c = 0
	l = list(map(int, input().split()))
	l1 = l[:]
	l2 = l[:]
	for j in range(0, n):
		if l[j] == l1[j]:
			for k in range(0, n):
				if l[k] != l1[j]:
					if l1[k] != l1[j]:
						temp = l1[k]
						l1[k] = l1[j]
						l1[j] = temp
						break
	for j in range(0, n):
		if l1[j] == l2[j]:
			c = c + 1
	print(n - c)
	for j in range(0, n):
		if j != n - 1:
			print(str(l1[j]) + ' ', end='')
		else:
			print(str(l1[j]), end='')
	if not i == t - 1:
		print()


def h(l1, l2):
	x = 0
	l = len(l1)
	for i in range(l):
		if l1[i] == l2[i]:
			x += 1
	return l - x
for i in range(int(input())):
	x = int(input())
	arr = input().split()
	arr2 = list(arr)
	for i in range(len(arr)):
		if arr[i] == arr2[i]:
			for j in range(0, len(arr)):
				if arr[i] != arr[j] and arr[i] != arr2[j]:
					(arr[i], arr[j]) = (arr[j], arr[i])
					break
	print(h(arr, arr2))
	print(' '.join(arr))


t = int(input())
for _ in range(t):
	n = int(input())
	st = input()
	s = st.split()
	a = [0] * n
	if n == 1:
		print(0)
		print(st)
	elif n == 2:
		if s[0] == s[1]:
			print(0)
			for i in s:
				print(i, end=' ')
			print()
		else:
			print(2)
			for i in s[::-1]:
				print(i, end=' ')
			print()
	elif n == 3:
		if s[0] == s[1] or s[1] == s[2] or s[0] == s[2]:
			print(2)
		else:
			print(3)
		r = n - 1
		for _ in range(n):
			print(s[r], end=' ')
			if r == n - 1:
				r = 0
			else:
				r += 1
		print()
	elif n > 3:
		print(n)
		if st[:len(st) // 2] == st[:len(st) // 2:-1]:
			p = []
			r = n // 2 + 1
			for _ in range(n):
				p.append(s[r])
				if r == n - 1:
					r = 0
				else:
					r += 1
			m = p[n - 1]
			p[n - 1] = p[n - 2]
			p[n - 2] = m
			for j in p:
				print(j, end=' ')
			print()
		elif s[0] == s[n - 1]:
			r = n - 2
			for _ in range(n):
				print(s[r], end=' ')
				if r == n - 1:
					r = 0
				else:
					r += 1
			print()
		else:
			for i in range(n):
				r = i + 1
				for _ in range(n - 1):
					if r > n - 1:
						r = 0
					if s[r] != s[i]:
						if a[r] == 0:
							a[r] = s[i]
							break
					r += 1
			for i in a:
				print(i, end=' ')
			print()


from collections import Counter
from operator import itemgetter
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = Counter(a).most_common(1)[0][1]
	print(min(n, 2 * (n - m)))
	b = sorted(enumerate(a), key=itemgetter(1))
	c = b[m:] + b[:m]
	d = sorted(((i, v) for ((i, _), (_, v)) in zip(b, c)))
	print(' '.join((str(x[1]) for x in d)))


for TestCase in range(int(input())):
	Size = int(input())
	L = list(map(int, input().split()))
	LCopy = list(L)
	e = []
	if Size == 1:
		print(0)
		print(*L)
	else:
		for i in range(Size):
			L[i] = str(LCopy[i - 1])
			if str(L[i]) == str(LCopy[i]):
				e.append(i)
		f = list(L)
		if len(e) <= 0:
			print(Size)
			print(*L)
		elif len(e) == 1:
			if Size == 3:
				print(2)
				print(*L)
			else:
				(L[e[0]], L[e[0] - 2]) = (L[e[0] - 2], L[e[0]])
				print(Size)
				print(*L)
		elif Size == 2:
			print(0)
			print(*LCopy)
		else:
			for i in range(len(e)):
				L[e[i]] = int(f[e[i - 1]])
			print(Size)
			print(*L)


def print_arr(arr):
	for i in arr:
		print(i, end=' ')
	print()

def repl(order_2, order_1, arr):
	b = []
	for i in order_2:
		b.append(i)
		b.append(i)
	for i in order_1:
		b.append(i)
	l = b[:]
	l.extend(b[0:2])
	l = l[2:]
	res = []
	d = {}
	for i in range(len(b)):
		if b[i] in d:
			d[b[i]].append(l[i])
		else:
			d[b[i]] = [l[i]]
	for i in arr:
		res.append(d[i][0])
		d[i] = d[i][1:]
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	order_2 = []
	order_1 = []
	replace = {}
	for i in d:
		if d[i] == 2:
			order_2.append(i)
		else:
			order_1.append(i)
	if len(a) == 1:
		print(0)
		print_arr(a)
		continue
	elif len(a) == 2:
		if len(order_2) == 1:
			print(0)
			print_arr(a)
			continue
		else:
			print(2)
			a.reverse()
			print_arr(a)
			continue
	b = repl(order_2, order_1, a)
	dist = 0
	for i in range(len(a)):
		if a[i] != b[i]:
			dist += 1
	print(dist)
	print_arr(b)


from collections import Counter, defaultdict
T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = A[:]
	B.sort()
	assign = defaultdict(list)
	B_len = len(B)
	if B_len > 2:
		for i in range(B_len):
			first = B[i]
			second = B[(i + 2) % B_len]
			assign[first].append(second)
		ans = []
		count = 0
		for a in A:
			val = assign[a].pop()
			if val != a:
				count += 1
			ans.append(str(val))
		print(count)
		print(' '.join(ans))
	elif len(A) == 1:
		print(0)
		print(A[0])
	else:
		print(2 if A[0] != A[1] else 0)
		print(A[1], A[0])


def callme():
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print('0')
		print(arr[0])
		return
	newarr = [0] * n
	if len(arr) == len(set(arr)):
		for i in range(n):
			newarr[i - 1] = arr[i]
		print(n)
		print(*newarr)
		return
	freq = {}
	for i in arr:
		if i not in freq.keys():
			freq[i] = 0
		freq[i] += 1
	newarr = [-1] * n
	x = 0
	for i in freq.keys():
		while freq[i] > 0 and x < n:
			if newarr[x] == -1 and i != arr[x]:
				newarr[x] = i
				freq[i] -= 1
			x += 1
	y = []
	for i in freq.keys():
		if freq[i] > 0:
			y.append(i)
	x = 0
	for i in y:
		while freq[i] > 0 and x < n:
			if newarr[x] == -1 and i != arr[x]:
				newarr[x] = i
				freq[i] -= 1
			x += 1
	y = []
	for i in freq.keys():
		if freq[i] > 0:
			y.append(i)
	x = 0
	if len(y) > 0:
		x = 0
		for i in y:
			while freq[i] > 0 and x < n:
				if newarr[x] == -1:
					newarr[x] = i
					freq[i] -= 1
				x += 1
	cost = 0
	for i in range(n):
		if arr[i] != newarr[i]:
			cost += 1
	print(cost)
	print(*newarr)
for _ in range(int(input())):
	callme()


for _ in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	d = list(list1)
	e = []
	if n == 1:
		print(0)
		print(*list1)
	else:
		for i in range(n):
			list1[i] = str(d[i - 1])
			if str(list1[i]) == str(d[i]):
				e.append(i)
		f = list(list1)
		if len(e) <= 0:
			print(n)
			print(*list1)
		elif len(e) == 1:
			if n == 3:
				print(2)
				print(*list1)
			else:
				(list1[e[0]], list1[e[0] - 2]) = (list1[e[0] - 2], list1[e[0]])
				print(n)
				print(*list1)
		elif n == 2:
			print(0)
			print(*d)
		else:
			for i in range(len(e)):
				list1[e[i]] = int(f[e[i - 1]])
			print(n)
			print(*list1)


from copy import deepcopy

def cycleshift(m):
	m.append(m[0])
	m = m[1:]
	return m

def hd(y, z):
	hd = 0
	for i in range(n):
		if y[i] != z[i]:
			hd += 1
	if hd == n:
		return 1
	else:
		return 0

def allUnique(a):
	a = cycleshift(a)
	print(n)
	print(' '.join(a))

def others(a):
	print(n)
	b = deepcopy(a)
	x = 0
	while x == 0:
		a = cycleshift(a)
		x = hd(a, b)
	print(' '.join(a))
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [i for i in input().split(' ')]
	if len(arr) == len(set(arr)) and n != 1:
		allUnique(arr)
	elif n == 1:
		print(0)
		print(' '.join(arr))
	elif n == 2:
		print(0)
		print(' '.join(arr))
	elif n == 3:
		print('2')
		arr = cycleshift(arr)
		print(' '.join(arr))
	else:
		others(arr)


for t in range(int(input())):
	m = int(100000.0)
	n = int(input())
	ar = list(map(int, input().split()))
	freq = [0 for i in range(m)]
	idxs = [[] for i in range(m)]
	idx = 0
	for a in ar:
		freq[a - 1] += 1
		idxs[a - 1].append(idx)
		idx += 1
	counts = []
	for i in range(m):
		if freq[i] > 0:
			counts.append([freq[i], i])
	counts.sort(reverse=True)
	j = 0
	ans = 0
	while j < len(counts) and len(counts) > 1:
		if j == len(counts) - 1:
			if counts[j][0] == 2:
				temp = idxs[counts[j][1]][:]
				idxs[counts[j][1]] = idxs[counts[0][1]]
				idxs[counts[0][1]] = temp
				ans += 2
				j += 1
				continue
			else:
				temp = idxs[counts[j][1]][0]
				idxs[counts[j][1]][0] = idxs[counts[0][1]][0]
				idxs[counts[0][1]][0] = temp
				j += 1
				ans += 1
				continue
		if counts[j][0] == 2 and counts[j + 1][0] == 2:
			temp = idxs[counts[j][1]][:]
			idxs[counts[j][1]] = idxs[counts[j + 1][1]]
			idxs[counts[j + 1][1]] = temp
			j += 2
			ans += 4
			continue
		if counts[j][0] == 2 and counts[j + 1][0] == 1:
			if j + 2 < len(counts):
				temp = idxs[counts[j][1]][:]
				idxs[counts[j][1]][0] = idxs[counts[j + 1][1]][0]
				idxs[counts[j][1]][1] = idxs[counts[j + 2][1]][0]
				idxs[counts[j + 1][1]][0] = temp[0]
				idxs[counts[j + 2][1]][0] = temp[1]
				j += 3
				ans += 4
				continue
			else:
				temp = idxs[counts[j][1]][:]
				idxs[counts[j][1]][0] = idxs[counts[j + 1][1]][0]
				idxs[counts[j][1]][1] = idxs[counts[0][1]][0]
				idxs[counts[j + 1][1]][0] = temp[0]
				idxs[counts[0][1]][0] = temp[1]
				j += 2
				ans += 3
				continue
		if counts[j][0] == 1:
			temp = idxs[counts[j][1]][:]
			idxs[counts[j][1]] = idxs[counts[j + 1][1]]
			idxs[counts[j + 1][1]] = temp
			j += 2
			ans += 2
			continue
	br = [0 for i in range(n)]
	for i in range(m):
		idx = idxs[i]
		if len(idx) == 1:
			br[idx[0]] = i + 1
		if len(idx) == 2:
			br[idx[0]] = i + 1
			br[idx[1]] = i + 1
	ans = 0
	for (a, b) in zip(ar, br):
		if a != b:
			ans += 1
	print(ans)
	print(' '.join((str(x) for x in br)))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	f = [None] * 100001
	s = [None, None]
	l = [None, None]
	cnt = 0
	b = 0
	for (i, x) in enumerate(a):
		if f[x] is not None:
			f[x] ^= 1
		else:
			cnt += 1
			if cnt == 3 and n > 3:
				b = 1
			f[x] = b
		j = f[x]
		if s[j] is None:
			s[j] = x
		else:
			a[l[j]] = x
		l[j] = i
	for i in (0, 1):
		if l[i] is not None:
			a[l[i]] = s[i]
	print(0 if cnt == 1 else cnt if n <= 3 else n)
	print(*a)


def hamdist(str1, str2):
	diffs = 0
	for (ch1, ch2) in zip(str1, str2):
		if ch1 != ch2:
			diffs += 1
	return diffs
t = int(input())
for i in range(t):
	n = int(input())
	s = [int(x) for x in input().split()]
	j = 1
	b = s.copy()
	s.append(s[0])
	if n > 2:
		while j < n:
			if s[j] != s[j + 1]:
				(s[j], s[j + 1]) = (s[j + 1], s[j])
				j += 2
			elif s[j] != s[j - 1]:
				(s[j], s[j - 1]) = (s[j - 1], s[j])
				j += 1
		if s[0] != s[n]:
			for i in range(n):
				if s[n] != s[i] and s[n] != b[i]:
					(s[n], s[i]) = (s[i], s[n])
					break
		elif s[0] == b[0]:
			for i in range(n):
				if s[0] != s[i] and s[0] != b[i]:
					(s[0], s[i]) = (s[i], s[0])
					break
		ss = s[:n]
		print(hamdist(ss, b))
		for kk in ss:
			print(kk, end=' ')
		print()
	elif n == 1:
		print(0)
		print(s[0])
	elif n == 2:
		if s[0] == s[1]:
			print(0)
			print(s[0], s[1])
		else:
			print(2)
			print(s[1], s[0])


for i in range(int(input())):
	n = int(input())
	l = [int(s) for s in input().split()]
	if len(l) == 3:
		ans1 = 0
		ans = l[1:] + [l[0]]
		for w in range(3):
			if ans[w] != l[w]:
				ans1 += 1
		print(ans1)
		print(ans[0], ans[1], ans[2])
	elif len(l) == 2:
		ans = [l[1], l[0]]
		if ans == l:
			print(0)
			print(ans[0], ans[1])
		else:
			print(2)
			print(ans[0], ans[1])
	elif len(l) == 1:
		print(0)
		print(l[0])
	else:
		ans = l.copy()
		r = []
		s = 0
		if n % 2 * (n - 1) > 0:
			s = n % 2 * (n - 1)
		for j in range(0, n - 1, 2):
			if ans[j] != ans[j + 1]:
				a = ans[j + 1]
				ans[j + 1] = ans[j]
				ans[j] = a
			else:
				r += [j, j + 1]
		r1 = []
		for k in range(len(r)):
			if k % 2 == 0:
				if r[k] not in r1 and r[k] - 1 not in r1:
					b = ans[r[k] - 1]
					ans[r[k] - 1] = ans[r[k]]
					ans[r[k]] = b
					r1 += [r[k], r[k] - 1]
			elif r[k] not in r1 and (r[k] + 1) % n not in r1:
				d = ans[(r[k] + 1) % n]
				ans[(r[k] + 1) % n] = ans[r[k]]
				ans[r[k]] = d
				r1 += [r[k], (r[k] + 1) % n]
		if s != 0:
			c = ans[s]
			ans[s] = ans[2]
			ans[2] = c
		print(n)
		for v in ans:
			print(v, end=' ')
		print()


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	l_copy = l[:]
	k = 0
	while k < n:
		if l[k] != l[(k + 1) % n]:
			(l[k], l[(k + 1) % n]) = (l[(k + 1) % n], l[k])
			k = k + 2
		else:
			(l[k], l[(k + 2) % n]) = (l[(k + 2) % n], l[k])
			(l[(k + 1) % n], l[(k + 3) % n]) = (l[(k + 3) % n], l[(k + 1) % n])
			k = k + 4
	s = ''
	count = 0
	for _ in range(n):
		if l[_] != l_copy[_]:
			count = count + 1
		s = s + str(l[_]) + ' '
	print(count)
	print(s)


t = int(input())
while t > 0:
	n = int(input())
	inp = input()
	inp = inp.split(' ')
	l = list(inp)
	m = n // 2
	for i in range(n):
		j = i + 1
		while j < n and (inp[i] == l[j] or inp[j] == l[i]):
			j += 1
		if j != n:
			(l[i], l[j]) = (l[j], l[i])
	if l[n - 1] == inp[n - 1]:
		for o in range(n - 1):
			if inp[o] != l[n - 1] and l[o] != inp[n - 1]:
				(l[o], l[n - 1]) = (l[n - 1], l[o])
				break
	p = 0
	for i in range(n):
		if inp[i] != l[i]:
			p += 1
	print(p)
	for i in range(n - 1):
		print(int(l[i]), end=' ')
	print(l[n - 1])
	t -= 1


def shift(seq, n=0):
	a = n % len(seq)
	return seq[-a:] + seq[:-a]
n = int(input())
while n:
	n = n - 1
	length = int(input())
	l = [int(x) for x in input().split()]
	maxi = 0
	ival = 0
	for i in range(1, length):
		if maxi == length:
			break
		dp = shift(l, i)
		count = 0
		for j in range(0, length):
			if dp[j] != l[j]:
				count = count + 1
		if count > maxi:
			maxi = count
			ival = i
	print(maxi)
	ans = str(shift(l, ival))
	print(ans.replace(',', '').replace('[', '').replace(']', ''))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[::-1]
	count = 0
	for (i, val) in enumerate(b):
		if val == a[i]:
			j = (i + 1) % n
			while j != i:
				if val != b[j] and val != a[j]:
					(b[j], b[i]) = (b[i], b[j])
					count += 1
					break
				j = (j + 1) % n
		else:
			count += 1
	print(count)
	for i in b:
		print(i, end=' ')
	print()


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
		print(*a)
	elif n == 2:
		if a[0] == a[1]:
			print(0)
			print(*a)
		else:
			print(n)
			print(*a[::-1])
	elif n == 3:
		if a[0] == a[1] or a[0] == a[2] or a[1] == a[2]:
			print(n - 1)
			temp = a[n - 1]
			for i in range(n - 1, 0, -1):
				a[i] = a[i - 1]
			a[0] = temp
			print(*a)
		else:
			print(n)
			temp = a[0]
			a[0] = a[1]
			a[1] = a[2]
			a[2] = temp
			print(*a)
	elif n == 4:
		print(n)
		b = [-1] * n
		c = 0
		if len(set(a)) == 4:
			print(*a[::-1])
		else:
			b = [-1] * n
			if a[3] == a[2]:
				b[0] = a[3]
				b[1] = a[2]
				b[2] = a[1]
				b[3] = a[0]
				print(*b)
			else:
				arr2 = [-1] * 4
				arr2[0] = a[0]
				arr2[1] = a[1]
				arr2[2] = a[2]
				arr2[3] = a[3]
				c = 0
				ele = arr2[c]
				while c != n:
					ele = arr2[c]
					for i in range(n):
						if a[i] != ele and b[i] == -1:
							b[i] = ele
							c += 1
							break
				print(*b)
	else:
		print(n)
		b = [-1] * n
		c = 0
		che = []
		temp = a[n - 1]
		for i in range(n - 1):
			b[i + 1] = a[i]
			if a[i + 1] == a[i]:
				che.append(i + 1)
				c += 1
		if a[n - 1] == a[0]:
			che.append(0)
			c += 1
		b[0] = temp
		if c > 0:
			if c == 1:
				for u in range(n):
					if u != che[0]:
						temp = u
						break
				if che[0] == n - 1:
					temp += 1
				(b[che[0]], b[temp]) = (b[temp], b[che[0]])
			elif c == 2:
				(b[che[0]], b[che[1]]) = (b[che[1]], b[che[0]])
			else:
				for i in range(c - 1):
					no = che[i]
					no1 = che[i + 1]
					(b[no], b[no1]) = (b[no1], b[no])
		print(*b)


from collections import Counter
for t in range(int(input())):
	l = int(input())
	A = [int(x) for x in input().split()]
	misfit = 0
	maxitem = Counter(A).most_common()[0][1]
	count = 0
	end = 0
	if maxitem == 1:
		end = 1
		if l == 1:
			print(0)
			print(*A)
		else:
			B = A[1:] + [A[0]]
			print(l)
			print(*B)
	if maxitem == l and l != 1:
		end = 1
		print(0)
		print(*A)
	if end == 0:
		if maxitem > l // 2:
			misfit = l - (l - maxitem) * 2
		C = 2 * A
		for i in range(1, l + 1):
			count = 0
			for x in range(l):
				if C[i + x] == A[x]:
					count += 1
					if misfit < count:
						break
			else:
				break
		print(l - misfit)
		print(*C[i:i + l])


t = int(input())
for test in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	indices = []
	sortArr = []
	hamDist = 0
	for i in sorted(enumerate(arr), key=lambda x: x[1]):
		indices.append(i[0])
		sortArr.append(i[1])
	pointer = 0
	i = 0
	while pointer < n:
		if arr[indices[i]] == sortArr[pointer]:
			pointer += 1
		else:
			arr[indices[i]] = sortArr[pointer]
			hamDist += 1
			pointer += 1
			i += 1
	pointer = 0
	for j in range(i, n):
		if arr[indices[j]] != sortArr[pointer]:
			hamDist += 1
		arr[indices[j]] = sortArr[pointer]
		pointer += 1
	print(hamDist)
	print(*arr)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	b = a[:]
	i = 0
	while i < n:
		while i < n and a[i] != b[i]:
			i += 1
		j = i + 1
		while j < n and b[j] == b[i]:
			j += 1
		if j < n:
			(b[i], b[j]) = (b[j], b[i])
		i += 1
	for i in range(n - 1, -1, -1):
		if b[i] == a[i]:
			j = i - 1
			while j >= 0 and (b[j] == b[i] or b[j] == a[i] or a[j] == b[i]):
				j -= 1
			if j >= 0:
				(b[j], b[i]) = (b[i], b[j])
		i += 1
	ans = 0
	for i in range(n):
		if a[i] != b[i]:
			ans += 1
	print(ans)
	print(*b)


for _ in range(int(input())):
	n = int(input())
	a = [int(s) for s in input().split()]
	b = []
	if n == 1:
		print(0)
		print(a[0])
	elif n == 2:
		if a[1] == a[0]:
			print(0)
		else:
			print(2)
		print(a[1], a[0])
	elif n == 3:
		if a[1] == a[0]:
			print(2)
			print(a[0], a[2], a[1])
		elif a[0] == a[2]:
			print(2)
			print(a[0], a[2], a[1])
		elif a[1] == a[2]:
			print(2)
			print(a[1], a[0], a[2])
		else:
			print(3)
			print(a[1], a[2], a[0])
	else:
		if n % 2 == 0:
			i = 0
			ad = 0
			while i < n:
				if a[i] == a[i + 1]:
					if b != []:
						tmp1 = b[-2]
						tmp2 = b[-1]
						(b[-1], b[-2]) = (a[i], a[i])
						b.append(tmp1)
						b.append(tmp2)
					elif ad == 1:
						b.append(a[i])
						b.append(a[i])
						b.append(a1)
						b.append(a1)
						ad = 0
					else:
						ad = 1
						a1 = a[i]
				else:
					b.append(a[i + 1])
					b.append(a[i])
					if ad == 1:
						ad = 0
						b.append(a1)
						b.append(a1)
				i += 2
		else:
			i = 0
			ad = 0
			while i < n - 1:
				if a[i] == a[i + 1]:
					if b != []:
						tmp1 = b[-2]
						tmp2 = b[-1]
						(b[-1], b[-2]) = (a[i], a[i])
						b.append(tmp1)
						b.append(tmp2)
					elif ad == 1:
						b.append(a[i])
						b.append(a[i])
						b.append(a1)
						b.append(a1)
						ad = 0
					else:
						ad = 1
						a1 = a[i]
				else:
					b.append(a[i + 1])
					b.append(a[i])
					if ad == 1:
						ad = 0
						b.append(a1)
						b.append(a1)
				i += 2
			if a[-2] == a[-1]:
				b.append(a[-1])
				temp = b[0]
				b[0] = b[-1]
				b[-1] = temp
			else:
				b.append(a[-1])
				temp = b[-2]
				b[-2] = b[-1]
				b[-1] = temp
		print(n)
		print(*b)


tests = int(input())
results = []
for i in range(0, tests):
	n = int(input())
	numso = input().split(' ')
	nums = list(numso)
	n = len(nums)
	l = 0
	r = n - 1
	while l < r:
		if nums[l] != nums[r]:
			(nums[l], nums[r]) = (nums[r], nums[l])
			l += 1
			r -= 1
		elif l + 1 < r - 1:
			(nums[l], nums[l + 1]) = (nums[l + 1], nums[l])
			(nums[r], nums[r - 1]) = (nums[r - 1], nums[r])
			l += 2
			r -= 2
		elif l - 1 >= 0 and r + 1 <= n - 1:
			(nums[l], nums[l - 1]) = (nums[l - 1], nums[l])
			(nums[r], nums[r + 1]) = (nums[r + 1], nums[r])
			l += 2
			r -= 2
		else:
			break
	if n % 2 == 1 and n >= 3:
		m = int(n / 2)
		mv = nums[m]
		for p in range(0, n):
			if mv != nums[p] and mv != numso[p]:
				(nums[m], nums[p]) = (nums[p], nums[m])
				break
	dist = 0
	for p in range(0, n):
		if nums[p] != numso[p]:
			dist += 1
	results.append(dist)
	results.append(' '.join(nums))
for i in range(0, len(results)):
	if i % 2 == 1:
		print(results[i])
	else:
		ll = results[i]
		print(ll)


import copy
T = int(input())

def ham(A, B):
	count = 0
	for i in range(0, len(A)):
		if A[i] != B[i]:
			count = count + 1
	return count
for i in range(0, T):
	N = int(input())
	a = input()
	a = list(map(int, a.split()))
	b = list(reversed(a))
	j = 0
	i = 0
	c = []
	while i < len(a):
		if b == []:
			break
		elif j == len(a) and len(c) < len(a):
			if len(b) > 1:
				c.append(b[-2])
				c.append(b[-1])
			else:
				c.append(b[-1])
			break
		elif j == len(b) and len(c) < len(a):
			if len(b) > 1:
				c.append(b[-2])
				c.append(b[-1])
			else:
				c.append(b[-1])
			break
		elif a[i] != b[j]:
			c.append(b.pop(j))
			i = i + 1
			j = 0
		elif i == len(a) - 1:
			c.append(b.pop(0))
		else:
			j = j + 1
	if a[-1] == c[-1]:
		for i in range(0, len(a) - 1):
			if c[-1] != a[i] and c[-1] != c[i]:
				(c[-1], c[i]) = (c[i], c[-1])
				break
	print(ham(c, a))
	print(*c)


for i in range(int(input())):
	n = int(input())
	l1 = []
	flag = 0
	f = 0
	l = [int(x) for x in input().split()]
	if n == 1:
		print(0)
		print(*l)
		flag = 1
	if n == 2 and n != len(set(l)) and (flag == 0):
		print(0)
		print(*l)
		flag = 1
	if n == len(set(l)) and flag == 0:
		print(n)
		for i in range(n - 1):
			l1.append(l[i + 1])
		l1.append(l[0])
		print(*l1)
	elif flag == 0:
		c = 1
		f = 0
		for i in range(n - 1):
			if l[i] == l[i + 1] or l[0] == l[-1]:
				f = 1
				break
			else:
				continue
		if f != 1 or (f == 1 and n == 3 and (len(set(l)) == 2)):
			if n != 3:
				print(n)
			else:
				print(2)
			for i in range(n - 1):
				l1.append(l[i + 1])
			l1.append(l[0])
			print(*l1)
		else:
			print(n)
			for i in range(n - 2):
				l1.append(l[i + 2])
			l1.append(l[0])
			l1.append(l[1])
			for i in range(n - 1):
				if l1[i] == l[i]:
					a = l1[i]
					l1[i] = l1[i + 1]
					l1[i + 1] = a
			print(*l1)


def count(a, b, n):
	c = 0
	for i in range(n):
		if a[i] != b[i]:
			c += 1
	return c
t = int(input())
for e in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
		print(a[0])
		continue
	dic = dict()
	(s, d) = ([], [])
	for i in range(n):
		if a[i] in dic:
			d.append([dic[a[i]], i])
			del dic[a[i]]
		else:
			dic[a[i]] = i
	for i in dic:
		s.append(dic[i])
	if len(d) == 0:
		print(n)
		for i in range(1, n):
			print(a[i], end=' ')
		print(a[0])
	else:
		b = list(a)
		(x, y) = (d[0][0], d[0][1])
		for i in range(1, len(d)):
			(e, f, p, q) = (d[i - 1][0], d[i - 1][1], d[i][0], d[i][1])
			(b[e], b[f]) = (a[p], a[q])
		l = len(d) - 1
		(i, j) = (d[l][0], d[l][1])
		(b[i], b[j]) = (a[x], a[y])
		l = len(s)
		if l == 1 and len(d) > 1:
			(i, j) = (s[0], d[0][0])
			(b[i], b[j]) = (b[j], b[i])
		if l > 1:
			for i in range(1, l):
				b[s[i - 1]] = a[s[i]]
			b[s[l - 1]] = a[s[0]]
		if len(d) == 1 and l > 0:
			(i, j) = (d[0][0], s[0])
			(b[i], b[j]) = (b[j], b[i])
			if l > 1:
				(i, j) = (d[0][1], s[1])
				(b[i], b[j]) = (b[j], b[i])
		print(count(a, b, n))
		for i in range(n):
			print(b[i], end=' ')
		print()


import random

def check(arr, li):
	count = 0
	for i in range(len(arr)):
		if arr[i] == li[i]:
			count += 1
	return count

def shuf(li):
	if len(li) > 3:
		arr = li[:]
		random.shuffle(arr)
		while True:
			random.shuffle(arr)
			if check(arr, li) == 0:
				break
		return arr
	elif len(li) == 1:
		return li
	elif len(li) == 2:
		if li[0] != li[1]:
			return li
		else:
			return li[::-1]
	elif len(li) == 3:
		if len(set(li)) == 3:
			return li
		else:
			return
t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	if len(li) > 3:
		ans = shuf(li)
		print(len(ans))
		print(*ans)
	elif len(li) == 1:
		print('0')
		print(*li)
	elif len(li) == 2:
		if li[0] != li[1]:
			print('2')
			print(li[1], li[0])
		else:
			print('0')
			print(*li)
	elif len(li) == 3:
		if li[0] == li[1] or li[1] == li[2]:
			print('2')
			print(li[2], li[1], li[0])
		elif li[0] == li[2]:
			print('2')
			print(li[1], li[2], li[0])
		else:
			print('3')
			print(li[2], li[0], li[1])


test = int(input())
while test > 0:
	n = int(input())
	new = [0 for i in range(n)]
	array = [int(a) for a in input().split()]
	i = 0
	if n == 1:
		print(0)
		print(array[0])
		test = test - 1
		continue
	while i < n:
		if array[i] == array[(i + 1) % n]:
			break
		else:
			i = i + 1
	i = i % n
	y = i
	status = 0
	dist = 0
	while True:
		if i >= n:
			i = i % n
			status = 1
		if status and i == y:
			break
		if array[i] != array[(i + 1) % n]:
			if new[(i + 1) % n]:
				if array[(i + 2) % n] == array[i]:
					new[(i + 2) % n] = array[(i + 1) % n]
					new[(i + 3) % n] = array[i]
					if (i + 3) % n == i:
						dist = dist + 1
					i = i + 1
				else:
					new[(i + 2) % n] = array[i]
				if array[i] == array[(i + 2) % n]:
					dist = dist + 1
			else:
				new[(i + 1) % n] = array[i]
		else:
			new[(i + 2) % n] = array[i]
			if array[i] == array[(i + 2) % n]:
				dist = dist + 1
		i = i + 1
	print(n - dist)
	for j in new:
		print(j, end=' ')
	print('')
	test = test - 1


t = int(input().strip())
pos = {}
d = {}
arr = []
swap = []

def swap1(x, y):
	(arr[pos[x][0]], arr[pos[y][0]]) = (arr[pos[y][0]], arr[pos[x][0]])
	(arr[pos[x][1]], arr[pos[y][1]]) = (arr[pos[y][1]], arr[pos[x][1]])
	swap[pos[x][0]] = 1
	swap[pos[y][0]] = 1
	swap[pos[x][1]] = 1
	swap[pos[y][1]] = 1

def swap2(x, y, z):
	(arr[pos[x][0]], arr[pos[y][0]]) = (arr[pos[y][0]], arr[pos[x][0]])
	(arr[pos[x][1]], arr[pos[z][0]]) = (arr[pos[z][0]], arr[pos[x][1]])
	swap[pos[x][0]] = 1
	swap[pos[y][0]] = 1
	swap[pos[x][1]] = 1
	swap[pos[z][0]] = 1

def swap3(x, y):
	(arr[x], arr[y]) = (arr[y], arr[x])
	swap[x] = 1
	swap[y] = 1
for _ in range(t):
	length = int(input().strip())
	arr = list(map(int, input().strip().split()))
	c = 0
	flag = False
	pos = {}
	d = {}
	swap = [0] * length
	single = []
	pair = []
	reserve = -1
	for i in arr:
		try:
			d[i] += 1
			pos[i].append(c)
		except:
			d[i] = 1
			pos[i] = [c]
		c += 1
	for i in list(set(arr)):
		if d[i] > 1:
			pair.append(i)
		else:
			single.append(i)
	l1 = len(pair)
	i = 0
	while i < l1 // 2:
		swap1(pair[2 * i], pair[2 * i + 1])
		if i == 0:
			reserve = pair[0]
		i += 1
	j = 0
	l2 = len(single)
	if l1 % 2 != 0 and l2 >= 2:
		swap2(pair[2 * i], single[2 * j], single[2 * j + 1])
		single = single[2:]
		l2 -= 2
	elif l1 % 2 != 0 and l2 == 1:
		swap3(pos[pair[2 * i]][0], pos[single[2 * j]][0])
		single = single[1:]
		l2 -= 1
		if reserve != -1:
			swap3(pos[pair[2 * i]][1], pos[reserve][0])
	elif l1 % 2 != 0 and l2 == 0 and (reserve != -1):
		swap1(pair[2 * i], reserve)
	while j < l2 // 2:
		if reserve == -1 and j == 0:
			reserve = single[0]
			flag = True
		swap3(pos[single[2 * j]][0], pos[single[2 * j + 1]][0])
		j += 1
	if l2 % 2 != 0 and reserve != -1:
		if flag:
			swap3(pos[single[2 * j]][0], pos[reserve][0])
		else:
			swap3(pos[single[2 * j]][0], pos[reserve][1])
	hamd = swap.count(0)
	print(length - hamd)
	for i in arr:
		print(i, end=' ')
	print()


t = int(input())
arr_list = []
hd_list = []
for i in range(t):
	n = int(input())
	inp_list = input().split()
	arr = ''
	hd = 0
	swap = 0
	if n == 1:
		hd_list.append(0)
		arr = inp_list[0]
	elif n == 2 and inp_list[0] == inp_list[1]:
		hd_list.append(0)
		arr = inp_list[0] + ' ' + inp_list[0]
	elif n == 2:
		hd_list.append(2)
		arr = inp_list[1] + ' ' + inp_list[0]
	elif n == 3 and inp_list[0] == inp_list[1]:
		hd_list.append(2)
		arr = inp_list[0] + ' ' + inp_list[-1] + ' ' + inp_list[0]
	elif n == 3 and inp_list[1] == inp_list[2]:
		hd_list.append(2)
		arr = inp_list[1] + ' ' + inp_list[0] + ' ' + inp_list[2]
	elif n == 3 and inp_list[0] == inp_list[2]:
		hd_list.append(2)
		arr = inp_list[0] + ' ' + inp_list[2] + ' ' + inp_list[1]
	elif n == 3:
		hd_list.append(3)
		arr = inp_list[2] + ' ' + inp_list[0] + ' ' + inp_list[1]
	else:
		hd_list.append(n)
		temp_list = inp_list.copy()
		j = 0
		flag = 0
		ctr = n
		while flag == 0:
			ctr -= 1
			if ctr == -1:
				temp_list = inp_list.copy()
				ctr = n
				(temp_list[1], temp_list[0]) = (temp_list[0], temp_list[1])
			temp_arr = temp_list[1:n]
			temp_arr.append(temp_list[0])
			flag = 1
			for j in range(n):
				if temp_arr[j] == inp_list[j]:
					temp_list = temp_arr
					flag = 0
					break
		for j in range(n - 1):
			arr = arr + temp_arr[j] + ' '
		arr += temp_arr[n - 1]
	arr_list.append(arr)
for i in range(t):
	print(hd_list[i])
	print(arr_list[i])


T = int(input())
for _testcase_ in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	if len(A) <= 3:
		if len(A) == 1:
			B = [A[0]]
			print(0)
		if len(A) == 2:
			if A[0] == A[1]:
				B = [A[1], A[0]]
				print(0)
			else:
				B = [A[1], A[0]]
				print(2)
		if len(A) == 3:
			if len(set(A)) == 3:
				B = [A[1], A[2], A[0]]
				print(3)
			elif len(set(A)) == 2:
				print(2)
				single = min(A, key=lambda x: A.count(x))
				double = max(A, key=lambda x: A.count(x))
				singleI = A.index(single)
				if singleI == 0:
					B = [double, single, double]
				else:
					B = [single, double, double]
		print(' '.join((str(x) for x in B)))
		continue
	B = [A[-1]] + A[:-1]
	badValues = []
	badIndices = []
	for i in range(N):
		if A[i] == B[i]:
			badValues.append(B[i])
			badIndices.append(i)
	if len(badValues) > 1:
		badIndices = [badIndices[-1]] + badIndices[:-1]
		for i in range(len(badIndices)):
			badIndex = badIndices[i]
			badValue = badValues[i]
			B[badIndex] = badValue
	elif len(badValues) == 1:
		for newI in range(N):
			if A[newI] != badValues[0] and A[badIndices[0]] != B[newI]:
				(B[newI], B[badIndices[0]]) = (badValues[0], B[newI])
				break
	elif len(badValues) < 1:
		pass
	print(N)
	print(' '.join((str(x) for x in B)))
	continue


from collections import defaultdict
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	p = len(l)
	l1 = sorted(l)
	if p == 1:
		print(0)
		print(l[0], end=' ')
	elif p == 2:
		if l[0] == l[1]:
			print(0)
		else:
			print(2)
		for k in reversed(l):
			print(k, end=' ')
	elif p == 3:
		l3 = defaultdict(list)
		l3[l1[p - 2]].append(l1[0])
		l3[l1[p - 1]].append(l1[1])
		for j in range(p - 2):
			l3[l1[j]].append(l1[j + 2])
		if l[0] == l[1] or l[1] == l[2] or l[2] == l[0]:
			print(2)
			for k in l:
				if l3[k][0] != -1:
					print(l3[k][0], end=' ')
					l3[k][0] = -1
				else:
					print(l3[k][1], end=' ')
		else:
			print(3)
			for k in l:
				print(l3[k][0], end=' ')
	else:
		l3 = defaultdict(list)
		l3[l1[p - 2]].append(l1[0])
		l3[l1[p - 1]].append(l1[1])
		for j in range(p - 2):
			l3[l1[j]].append(l1[j + 2])
		print(p)
		for j in l:
			if l3[j][0] == -1:
				print(l3[j][1], end=' ')
			else:
				print(l3[j][0], end=' ')
				l3[j][0] = -1
	print()


test = int(input())
for _ in range(test):
	S = int(input())
	arr = {}
	two = {}
	hd = 0
	c = 1
	for i in input().split():
		i = int(i)
		if i in arr:
			temp = arr[i][1]
			arr.pop(i)
			two[i] = {2: [temp, c]}
		else:
			arr[i] = {1: c}
		c += 1
	res = [0] * S
	hd = 0
	lastc = lasta = 0
	lastx = lasty = lastx1 = -1
	lt = list(two.keys())
	lent = len(lt)
	lent_c = 0
	lentwo = len(two)
	while two != {} and lentwo > 1:
		if lent_c < lent - 1:
			x = two.pop(lt[lent_c])
			k1 = lt[lent_c]
			if lastc == 0:
				(lastx, lasty) = x[2]
				lastc = 1
			(indy1, indy2) = two[lt[lent_c + 1]][2]
			res[indy1 - 1] = k1
			res[indy2 - 1] = k1
			hd += 2
		else:
			x = two.popitem()
			res[lastx - 1] = x[0]
			res[lasty - 1] = x[0]
			hd += 2
		lent_c += 1
	arrl = []
	lenarr = len(arr)
	l = list(arr.keys())
	lenl = len(l)
	lenl_c = 0
	while arr != {} and lenarr > 1:
		hd += 1
		if lenl_c < lenl - 1:
			x = arr.pop(l[lenl_c])
			k1 = l[lenl_c]
			if lasta == 0:
				lastx1 = x[1]
				lasta = 1
			indy1 = arr[l[lenl_c + 1]][1]
			res[indy1 - 1] = k1
			arrl.append(indy1 - 1)
		else:
			x = arr.popitem()
			if lastx1 != -1:
				res[lastx1 - 1] = x[0]
				arrl.append(lastx1 - 1)
		lenl_c += 1
	if len(two) == 1 and lenarr > 1:
		t = two.popitem()
		(indt1, indt2) = t[1][2]
		valt = t[0]
		(x, y) = (res[arrl[0]], res[arrl[1]])
		(res[arrl[0]], res[arrl[1]], res[indt1 - 1], res[indt2 - 1]) = (valt, valt, x, y)
		hd += 2
	elif len(two) == 1 and len(arr) == 1:
		t = two.popitem()
		(indt1, indt2) = t[1][2]
		valt = t[0]
		a = arr.popitem()
		inda = a[1][1]
		vala = a[0]
		(res[indt1 - 1], res[indt2 - 1], res[inda - 1]) = (valt, vala, valt)
		hd = 2
	elif len(two) == 1 and lenarr == 0:
		t = two.popitem()
		(indt1, indt2) = t[1][2]
		valt = t[0]
		res[0] = res[1] = valt
		hd = 0
	elif len(arr) == 1 and two == {}:
		if S == 1:
			res[0] = arr.popitem()[0]
			hd = 0
		elif S > 1:
			a = arr.popitem()
			inda = a[1][1]
			vala = a[0]
			if inda < S - 1:
				(res[inda], res[inda - 1]) = (a[0], res[inda])
			elif inda == S:
				(res[0], res[inda - 1]) = (a[0], res[0])
				hd += 1
	print(hd)
	print(*res)


for q in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = list(set(a))
	c = [a[i] for i in range(n)]
	lb = len(b)
	flag = [0 for i in range(n)]
	count = 0
	count1 = 0
	if n == 1:
		print(0)
		for k in a:
			print(k, end=' ')
		print()
	elif n == lb:
		print(n)
		for k in range(1, n):
			print(a[k], end=' ')
		print(a[0])
	elif n == 2 and lb == 1:
		print(0)
		for k in a:
			print(k, end=' ')
		print()
	elif n == 3 and lb == 2:
		if a[0] == a[1]:
			print(2)
			print(a[0], end=' ')
			print(a[2], end=' ')
			print(a[1])
		if a[0] == a[2] or a[1] == a[2]:
			print(2)
			print(a[1], end=' ')
			print(a[0], end=' ')
			print(a[2])
	elif n == 4 and lb == 3 and (a[3] == a[2]):
		print(4)
		print(a[2], end=' ')
		print(a[3], end=' ')
		print(a[0], end=' ')
		print(a[1])
	else:
		print(n)
		i = 1
		while i < n:
			if i == n - 1 and flag[i - 1] == 1:
				break
			if i == n - 1 and flag[i - 1] == 0 and (c[i] != c[i - 1]):
				(c[i], c[i - 1]) = (c[i - 1], c[i])
				flag[i - 1] = 1
				flag[i] = 1
				break
			if c[i] == c[i - 1]:
				i += 1
			else:
				(c[i], c[i - 1]) = (c[i - 1], c[i])
				flag[i - 1] = 1
				flag[i] = 1
				i += 2
		for i in range(n):
			if c[i] != a[i]:
				count1 += 1
		if count1 == n:
			for d in c:
				print(d, end=' ')
			print()
		else:
			ind = []
			for i in range(n):
				if flag[i] == 0:
					count += 1
			if count % 2 == 0 and count > 0:
				for i in range(n):
					if flag[i] == 0:
						ind.append(i)
				l = len(ind)
				i = 1
				while i < l:
					(c[ind[i]], c[ind[i - 1]]) = (c[ind[i - 1]], c[ind[i]])
					flag[ind[i - 1]] = 1
					flag[ind[i]] = 1
					i += 2
			else:
				for i in range(n):
					if flag[i] == 0:
						ind.append(i)
				l = len(ind)
				if l == 1:
					for i in range(n):
						if c[ind[0]] != a[i] and c[ind[0]] != c[i]:
							(c[ind[0]], c[i]) = (c[i], c[ind[0]])
							flag[ind[0]] = 1
							break
				else:
					i = 1
					while i < l - 1:
						(c[ind[i]], c[ind[i - 1]]) = (c[ind[i - 1]], c[ind[i]])
						flag[ind[i - 1]] = 1
						flag[ind[i]] = 1
						i += 2
					for i in range(n):
						if c[ind[l - 1]] != a[i] and c[ind[l - 1]] != c[i]:
							(c[ind[l - 1]], c[i]) = (c[i], c[ind[l - 1]])
							flag[ind[l - 1]] = 1
							break
			for d in c:
				print(d, end=' ')
			print()


from operator import itemgetter

def get_tuples(A):
	d = {}
	for i in A:
		d[i] = d.get(i, 0) + 1
	return d

def get_bi_from(sorted_tup, ai):
	res = -1
	for (i, (k, v)) in enumerate(sorted_tup):
		if k == ai:
			continue
		else:
			res = k
			if v == 1:
				sorted_tup.pop(i)
			else:
				sorted_tup[i] = (k, v - 1)
			break
	return res

def find_swap(A, B, ind):
	n = len(A)
	t = B[ind]
	for i in range(n):
		if A[i] != t and A[ind] != B[i]:
			tmp = B[i]
			B[i] = t
			B[ind] = tmp
			return 1
	return 0
T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	tup = get_tuples(A)
	sorted_tup = sorted(tup.items(), key=itemgetter(1), reverse=True)
	hammer_dist = len(A)
	B = [-1 for i in range(len(A))]
	for (i, ai) in enumerate(A):
		bi = get_bi_from(sorted_tup, ai)
		if bi == -1:
			hammer_dist -= 1
			bi = ai
		B[i] = bi
	if N >= 2:
		if A[-1] == B[-1]:
			r = find_swap(A, B, N - 1)
			hammer_dist += r
		if A[-2] == B[-2]:
			r = find_swap(A, B, N - 2)
			hammer_dist += r
	print(hammer_dist)
	print(' '.join(list(map(str, B))))


t = int(input())
for i in range(t):
	n = int(input())
	s = input().split()
	s = [int(x) for x in s]
	if n == 1:
		print('0')
		print(s[0])
		continue
	elif n == 2 and s[0] == s[1]:
		print('0')
		print(s[0], s[1])
		continue
	elif n == 2:
		print('2')
		print(s[1], s[0])
		continue
	elif n == 3 and s[0] == s[1]:
		print('2')
		print(s[0], s[2], s[1])
		continue
	elif n == 3 and s[0] == s[2]:
		print('2')
		print(s[1], s[0], s[2])
		continue
	elif n == 3 and s[1] == s[2]:
		print('2')
		print(s[1], s[0], s[2])
		continue
	elif n == 3:
		print('3')
		print(s[1], s[2], s[0])
		continue
	j = 0
	count = 0
	temp = 0
	while j < n:
		if j + 1 < n:
			if s[j] != s[j + 1]:
				temp = s[j]
				s[j] = s[j + 1]
				s[j + 1] = temp
				count += 2
				j += 2
			elif j + 3 < n:
				temp = s[j]
				s[j] = s[j + 2]
				s[j + 2] = temp
				temp = s[j + 1]
				s[j + 1] = s[j + 3]
				s[j + 3] = temp
				count += 4
				j += 4
			elif j + 2 < n:
				temp = s[j]
				s[j] = s[j + 2]
				s[j + 2] = temp
				if s[j + 1] != s[0]:
					temp = s[j + 1]
					s[j + 1] = s[0]
					s[0] = temp
				else:
					temp = s[j + 1]
					s[j + 1] = s[1]
					s[1] = temp
				count += 3
				j += 3
			else:
				temp = s[j]
				s[j] = s[0]
				s[0] = temp
				temp = s[j + 1]
				s[j + 1] = s[1]
				s[1] = temp
				count += 2
				j += 2
		else:
			if s[j] != s[0]:
				temp = s[j]
				s[j] = s[0]
				s[0] = temp
			else:
				temp = s[j]
				s[j] = s[1]
				s[1] = temp
			count += 1
			j += 1
	print(count)
	for i in range(n):
		print(s[i], end='')
		print(' ', end='')
	print()


def check(x, y):
	count = 0
	for i in range(len(x)):
		if x[i] != y[i]:
			count += 1
	return count
t = int(input())
for k in range(t):
	n = int(input())
	b = [int(x) for x in input().split()]
	a = [b[i] for i in range(1, n)]
	a.append(b[0])
	if n > 2:
		for i in range(n):
			if a[i] == b[i]:
				for j in range(n):
					if j != i and a[i] != b[j] and (b[i] != a[j]):
						(a[i], a[j]) = (a[j], a[i])
						break
	print(check(a, b))
	for j in a:
		print(j, end=' ')
	print()


t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	if len(A) == 1:
		print(0)
		print(*A)
	elif len(A) == 2:
		if A.count(A[0]) == 2:
			print(0)
			print(*A)
		else:
			(A[0], A[1]) = (A[1], A[0])
			print(2)
			print(*A)
	elif len(A) == 3:
		if A.count(A[0]) == 2 or A.count(A[1]) == 2:
			print(2)
			if A[0] == A[1]:
				(A[0], A[2]) = (A[2], A[0])
			elif A[0] == A[2]:
				(A[0], A[1]) = (A[1], A[0])
			elif A[1] == A[2]:
				(A[0], A[2]) = (A[2], A[0])
			print(*A)
		else:
			print(3)
			(A[0], A[1], A[2]) = (A[1], A[2], A[0])
			print(*A)
	else:
		print(len(A))
		ACopy = list(A)
		for k in range(len(A)):
			if ACopy[k] == A[k]:
				for j in range(len(A)):
					if j != k and ACopy[j] != A[k] and (ACopy[k] != A[j]):
						(ACopy[k], ACopy[j]) = (ACopy[j], ACopy[k])
		print(*ACopy)


from collections import Counter
for test in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = Counter(a)
	(l, ans) = (0, n)
	(re, i) = ([0] * n, 0)
	for k in b:
		if b[k] > n / 2:
			l = 2 * b[k] - n
			ans = n - l
		while b[k] != 0:
			if re[i] == 0:
				if a[i] == k and l != 0:
					re[i] = k
					l -= 1
					b[k] -= 1
				elif a[i] != k:
					re[i] = k
					b[k] -= 1
			i = (i + 1) % n
	print(ans)
	print(*re)


import itertools
T = int(input())

def hamming(A, B):
	N = 0
	for (a, b) in zip(A, B):
		if a != b:
			N += 1
	return N
for t in range(T):
	N = int(input())
	vals = list((int(x) for x in input().split()))
	i = 0
	j = len(vals) - 1
	left = []
	right = []
	permut = False
	while i <= j:
		left.append(vals[j])
		if i != j:
			right.append(vals[i])
		i = i + 1
		j = j - 1
	res = left[::-1] + right
	h = hamming(res, vals)
	print(h)
	print(' '.join((str(x) for x in res)))


T = int(input())
for ai in range(T):
	N = int(input())
	inp = input()
	S = [int(m) for m in inp.split()]
	T = [int(m) for m in inp.split()]
	visit = []
	for i in range(N):
		if S[i] == T[i] and i < N - 1:
			try:
				if S[i] != S[i + 1] and S[i + 1] != T[i] and (S[i] != T[i + 1]):
					a = S[i]
					S[i] = S[i + 1]
					S[i + 1] = a
				elif S[i] != S[-1] and S[-1] != T[i] and (S[i] != T[-1]):
					a = S[i]
					S[i] = S[-1]
					S[-1] = a
				elif S[i] != S[i - 1] and S[i - 1] != T[i] and (S[i] != T[i - 1]):
					a = S[i]
					S[i] = S[i - 1]
					S[i - 1] = a
				elif S[i] != S[i - 2] and S[i - 2] != T[i] and (S[i] != T[i - 2]):
					a = S[i]
					S[i] = S[i - 2]
					S[i - 2] = a
			except IndexError:
				pass
		elif S[i] == T[i]:
			try:
				if S[i] != S[-2] and S[-2] != T[i] and (S[i] != T[-2]):
					a = S[i]
					S[i] = S[-2]
					S[-2] = a
				elif S[i] != S[-3] and S[-3] != T[i] and (S[i] != T[-3]):
					a = S[i]
					S[i] = S[-3]
					S[-3] = a
				elif S[i] != S[-4] and S[-4] != T[i] and (S[i] != T[-4]):
					a = S[i]
					S[i] = S[-4]
					S[-4] = a
			except IndexError:
				pass
	hd = 0
	for i in range(N):
		if S[i] != T[i]:
			hd += 1
	print(hd)
	print(' '.join(map(str, S)))