You are given an array $a$ of $n$ integers.

Find two permutations$^\dagger$ $p$ and $q$ of length $n$ such that $\max(p_i,q_i)=a_i$ for all $1 \leq i \leq n$ or report that such $p$ and $q$ do not exist.

$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq n$) — the array $a$.

It is guaranteed that the total sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, if there do not exist $p$ and $q$ that satisfy the conditions, output "NO" (without quotes).

Otherwise, output "YES" (without quotes) and then output $2$ lines. The first line should contain $n$ integers $p_1,p_2,\ldots,p_n$ and the second line should contain $n$ integers $q_1,q_2,\ldots,q_n$.

If there are multiple solutions, you may output any of them.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).


-----Examples-----

Input
3
1
1
5
5 3 4 2 5
2
1 1
Output
YES
1 
1 
YES
1 3 4 2 5 
5 2 3 1 4 
NO


-----Note-----

In the first test case, $p=q=[1]$. It is correct since $a_1 = max(p_1,q_1) = 1$.

In the second test case, $p=[1,3,4,2,5]$ and $q=[5,2,3,1,4]$. It is correct since:

$a_1 = \max(p_1, q_1) = \max(1, 5) = 5$,

$a_2 = \max(p_2, q_2) = \max(3, 2) = 3$,

$a_3 = \max(p_3, q_3) = \max(4, 3) = 4$,

$a_4 = \max(p_4, q_4) = \max(2, 1) = 2$,

$a_5 = \max(p_5, q_5) = \max(5, 4) = 5$.

In the third test case, one can show that no such $p$ and $q$ exist.

Difficulty: EASY
Tags: Greedy algorithms

Sorting

Implementation

Constructive algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
from sys import stdin

def solve():
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	pos = [[] for _ in range(n)]
	for (i, x) in enumerate(a):
		pos[x - 1].append(i)
	p1 = [-1] * n
	s1 = []
	p2 = [-1] * n
	s2 = []
	for (x_, px) in enumerate(pos[::-1]):
		x = n - x_
		if len(px) == 1:
			p1[px[0]] = p2[px[0]] = x
		elif len(px) == 2:
			p1[px[0]] = p2[px[1]] = x
			s1.append(px[1])
			s2.append(px[0])
		elif len(px) == 0 and s1 and s2:
			p1[s1.pop()] = x
			p2[s2.pop()] = x
		else:
			print('NO')
			return
	print('YES')
	print(' '.join(map(str, p1)))
	print(' '.join(map(str, p2)))

def main():
	t = int(stdin.readline())
	for _ in range(t):
		solve()
main()


t = int(input())
res = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	freq = [[] for _ in range(n + 2)]
	for (ind, e) in enumerate(a):
		freq[e].append(ind)
	p = [0] * n
	q = [0] * n
	minv = []
	ans = 'YES'
	for (i, e) in enumerate(freq):
		if i == 0:
			continue
		val = len(e)
		if val == 0:
			minv.append(i)
		elif val == 1:
			p[e[0]] = i
			q[e[0]] = i
		elif val == 2 and len(minv) != 0:
			p[e[0]] = i
			ele = minv.pop()
			p[e[0]] = i
			q[e[0]] = ele
			p[e[1]] = ele
			q[e[1]] = i
		else:
			ans = 'NO'
			break
	if ans == 'NO':
		res.append(ans)
	else:
		res.append(ans)
		res.append(' '.join(map(str, p)))
		res.append(' '.join(map(str, q)))
for i in res:
	print(i)


from collections import defaultdict

def solve():
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	p = [-1] * n
	q = [-1] * n
	p_empty_indexes = []
	q_empty_indexes = []
	val_to_indexes = defaultdict(list)
	for idx in range(n):
		val_to_indexes[arr[idx]].append(idx)
	for val in reversed(range(1, n + 1)):
		occurances = len(val_to_indexes[val]) if val in val_to_indexes else 0
		if occurances == 2:
			p[val_to_indexes[val][0]] = val
			q[val_to_indexes[val][1]] = val
			p_empty_indexes.append(val_to_indexes[val][1])
			q_empty_indexes.append(val_to_indexes[val][0])
		elif occurances == 1:
			p[val_to_indexes[val][0]] = val
			q[val_to_indexes[val][0]] = val
		elif occurances == 0:
			if len(p_empty_indexes) == 0 or len(q_empty_indexes) == 0:
				return (None, None)
			p_idx = p_empty_indexes.pop()
			q_idx = q_empty_indexes.pop()
			p[p_idx] = val
			q[q_idx] = val
	if len(p_empty_indexes) != 0 or len(q_empty_indexes) != 0:
		return (None, None)
	ps = [str(i) for i in p]
	qs = [str(i) for i in q]
	return (ps, qs)
tc = int(input())
for idx in range(tc):
	(p, q) = solve()
	if p is None:
		print('NO')
	else:
		print('YES')
		print(' '.join(p))
		print(' '.join(q))


from collections import defaultdict

def main():
	if max(A) != n:
		print('NO')
		return
	mp = defaultdict(list)
	for (i, x) in enumerate(A):
		mp[x].append(i)
		if len(mp[x]) > 2:
			print('NO')
			return
	p = [-1] * N
	q = [-1] * N
	pp = [-1] * N
	qq = [-1] * N
	for x in range(n, 0, -1):
		for i in mp[x]:
			if pp[x] == -1:
				pp[x] = i
				p[i] = x
			elif qq[x] == -1:
				qq[x] = i
				q[i] = x
	vp = vq = n
	for x in range(n, 0, -1):
		for i in mp[x]:
			while pp[vp] != -1:
				vp -= 1
			while qq[vq] != -1:
				vq -= 1
			if p[i] == -1 and vp > 0:
				pp[vp] = i
				p[i] = vp
			if q[i] == -1 and vq > 0:
				qq[vq] = i
				q[i] = vq
	for i in range(1, N):
		if max(p[i], q[i]) != A[i]:
			print('NO')
			return
	print('YES')
	print(' '.join(map(str, p[1:])))
	print(' '.join(map(str, q[1:])))
	return
t = int(input())
for case in range(t):
	n = int(input())
	N = n + 1
	A = [0] + list(map(int, input().split()))
	main()


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().strip().split()))
	probe = {v: [] for v in range(1, n + 1)}
	YES = True
	for (i, v) in enumerate(lst):
		probe[v].append(i)
		if len(probe[v]) > 2:
			YES = False
			break
	if not YES:
		print('NO')
		continue
	p = [None] * n
	q = [None] * n
	p_buffer = deque()
	q_buffer = deque()
	for v in range(n, 0, -1):
		if len(probe[v]) == 0 and (len(p_buffer) == 0 or len(q_buffer) == 0):
			YES = False
			break
		elif len(probe[v]) == 0:
			p[p_buffer.popleft()] = v
			q[q_buffer.popleft()] = v
		elif len(probe[v]) == 2:
			p[probe[v][0]] = v
			q[probe[v][1]] = v
			p_buffer.append(probe[v][1])
			q_buffer.append(probe[v][0])
		else:
			p[probe[v][0]] = v
			q[probe[v][0]] = v
	if not YES:
		print('NO')
		continue
	for i in range(len(lst)):
		if lst[i] != max(p[i], q[i]):
			YES = False
			break
	if not YES:
		print('NO')
	else:
		print('YES')
		print(' '.join(map(str, p)))
		print(' '.join(map(str, q)))


def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	a1 = a.copy()
	a1.sort()
	x = []
	y = []
	x_dict = {}
	y_dict = {}
	a_count = {}
	doubleval = []
	for i in a1:
		if i not in a_count:
			a_count[i] = 1
		elif a_count[i] == 1:
			a_count[i] += 1
			doubleval.append(i)
		else:
			print('NO')
			return
	hat = []
	for i in range(1, n + 1):
		if i not in a_count:
			hat.append(i)
	if len(hat) != len(doubleval):
		print('NO')
		return
	lookup_dict = {}
	for i in range(len(hat)):
		lookup_dict[doubleval[i]] = hat[i]
	for i in a:
		if a_count[i] == 1:
			x.append(i)
			y.append(i)
			continue
		if i not in x_dict:
			x_dict[i] = 1
			x.append(i)
			y.append(lookup_dict[i])
		elif i not in y_dict:
			y_dict[i] = 1
			y.append(i)
			x.append(lookup_dict[i])
		if max(i, lookup_dict[i]) != i:
			print('NO')
			return
	print('YES')
	print(*x)
	print(*y)
for _ in range(int(input())):
	solve()


import math
for i in range(int(input())):
	n = int(input())
	values = list(map(int, input().split()))
	adj = [[] for i in range(n + 1)]
	for k in range(n):
		adj[values[k]].append(k)
	valid = True
	P = []
	Q = []
	p = [0] * n
	q = [0] * n
	for i in range(n, 0, -1):
		count = len(adj[i])
		if count == 2:
			pos1 = adj[i][0]
			pos2 = adj[i][1]
			p[pos1] = i
			P.append(pos2)
			q[pos2] = i
			Q.append(pos1)
			continue
		if count == 1:
			pos = adj[i][0]
			p[pos] = i
			q[pos] = i
			continue
		if len(P) > 0 and len(Q) > 0:
			p[P.pop()] = i
			q[Q.pop()] = i
		else:
			valid = False
			break
	if valid:
		print('YES')
		print(*p)
		print(*q)
	else:
		print('NO')


def taskC():
	n = int(input())
	a = [int(i) for i in input().split()]
	if n == 1:
		if a[0] == 1:
			print('YES')
			print('1')
			print('1')
		else:
			print('NO')
		return
	b = sorted(a)
	pos = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		if b[i - 1] < i:
			print('NO')
			return
		if pos[b[i - 1]] == 2:
			print('NO')
			return
		else:
			pos[b[i - 1]] += 1
	print('YES')
	pairs = [0 for i in range(n + 1)]
	zeroes = []
	for i in range(1, n + 1):
		if pos[i] == 0:
			zeroes.append(i)
		elif pos[i] == 2:
			zero = zeroes.pop()
			pairs[i] = zero
	used = [False for i in range(0, n + 1)]
	p = [0 for i in range(n)]
	q = [0 for i in range(n)]
	for v in range(0, n):
		val = a[v]
		if pos[val] == 1:
			p[v] = val
			q[v] = val
		elif pos[val] == 2:
			pair = [val, pairs[val]]
			if used[val]:
				p[v] = pair[0]
				q[v] = pair[1]
			else:
				p[v] = pair[1]
				q[v] = pair[0]
				used[val] = True
	print(*p)
	print(*q)
t = int(input())
for i in range(t):
	taskC()


k = int(input())
for _ in range(k):
	ok = True
	n = int(input())
	a = list(map(int, input().split()))
	p = [0] * n
	q = [0] * n
	pos = [[] for i in range(n + 1)]
	for i in range(n):
		pos[a[i]].append(i)
	(rp, rq) = ([], [])
	for i in range(n, 0, -1):
		if len(pos[i]) == 2:
			p[pos[i][0]] = i
			q[pos[i][1]] = i
			rq.append(pos[i][0])
			rp.append(pos[i][1])
			continue
		if len(pos[i]) == 1:
			p[pos[i][0]] = i
			q[pos[i][0]] = i
			continue
		if len(rp) > 0 and len(rq) > 0:
			p[rp.pop()] = i
			q[rq.pop()] = i
		else:
			ok = False
	if ok:
		print('YES')
		print(*p)
		print(*q)
	else:
		print('NO')


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(v) for v in input().split()]
	arrset = set(arr)
	arrsort = sorted(((v, i) for (i, v) in enumerate(arr)))
	p = [-1] * n
	q = [-1] * n
	mp = 1
	mq = 1
	fooderp = deque()
	fooderq = deque()
	possible = True
	for (v, i) in arrsort:
		while mp <= v:
			fooderp.append(mp)
			mp += 1
		while mq <= v:
			fooderq.append(mq)
			mq += 1
		if len(fooderq) != 0 and len(fooderp) != 0 and (fooderp[-1] == v):
			p[i] = fooderp.pop()
			q[i] = fooderq.popleft()
		elif len(fooderp) != 0 and len(fooderq) != 0 and (fooderq[-1] == v):
			q[i] = fooderq.pop()
			p[i] = fooderp.popleft()
		else:
			possible = False
			break
	if not possible:
		print('NO')
	else:
		print('YES')
		print(' '.join([str(v) for v in p]))
		print(' '.join([str(v) for v in q]))


import sys
from heapq import *
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	cnt = [0] * (n + 1)
	flag = 1
	ans = [0] + [i for i in range(1, n + 1)]
	visit = [0] * (n + 1)
	for a in A:
		cnt[a] += 1
		if cnt[a] == 3:
			flag = 0
			break
	if flag == 1:
		H = []
		for i in range(1, n + 1):
			if cnt[i] == 0:
				heappush(H, i)
			elif cnt[i] == 1:
				pass
			elif cnt[i] == 2 and H:
				x = H.pop()
				ans[i] = x
				ans[x] = i
			else:
				flag = 0
				break
		if flag == 1:
			(p, q) = ([], [])
			for i in range(n):
				if visit[A[i]] == 0:
					p.append(A[i])
					q.append(ans[A[i]])
				else:
					q.append(A[i])
					p.append(ans[A[i]])
				visit[A[i]] += 1
				visit[ans[A[i]]] += 1
			print('YES')
			print(*p)
			print(*q)
	if flag == 0:
		print('NO')


import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

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

def readStr():
	return input().strip()

def solve():
	n = readInt()
	arr = readList()
	pos = [[] for _ in range(n + 1)]
	for i in range(n - 1, -1, -1):
		pos[arr[i]].append(i)
	s = 0
	exc = []
	for v in range(n, 0, -1):
		if len(pos[v]) == 2:
			s += 1
		elif len(pos[v]) == 1:
			continue
		elif len(pos[v]) == 0 and s:
			s -= 1
			exc.append(v)
		else:
			print('NO')
			return
	if s:
		print('NO')
		return
	ans = [[0] * n, [0] * n]
	for i in range(1, n + 1):
		if len(pos[i]) == 1:
			ans[0][pos[i][0]] = i
			ans[1][pos[i][0]] = i
		elif len(pos[i]) == 2:
			v = exc.pop()
			ans[0][pos[i][0]] = i
			ans[1][pos[i][0]] = v
			ans[0][pos[i][1]] = v
			ans[1][pos[i][1]] = i
	print('YES')
	print(*ans[0])
	print(*ans[1])
for _ in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(p, q) = ([0] * n, [0] * n)
	pos = [[] for i in range(n + 1)]
	for i in range(n):
		pos[a[i]].append(i)
	(rp, rq) = ([], [])
	for i in range(n, 0, -1):
		if len(pos[i]) == 2:
			p[pos[i][0]] = i
			q[pos[i][1]] = i
			rp.append(pos[i][1])
			rq.append(pos[i][0])
		elif len(pos[i]) == 1:
			p[pos[i][0]] = i
			q[pos[i][0]] = i
		elif len(rp) > 0 and len(rq) > 0:
			p[rp.pop()] = i
			q[rq.pop()] = i
		else:
			print('NO')
			break
	else:
		print('YES')
		print(*p)
		print(*q)


def display(a, b, d):
	(x, y) = ([0] * n, [0] * n)
	for i in range(n):
		if b[a[i] - 1] == 1:
			x[i] = a[i]
			y[i] = a[i]
		elif b[a[i] - 1] == 2:
			x[i] = a[i]
			y[i] = d[a[i] - 1]
			b[a[i] - 1] -= 2
		else:
			x[i] = d[a[i] - 1]
			y[i] = a[i]
	return (x, y)

def do(b, c):
	(d, count) = ([0] * n, 0)
	for i in range(n):
		if b[i] == 1:
			d[i] = i + 1
		elif b[i] == 2:
			d[i] = c[count] + 1
			d[c[count]] = i + 1
			count += 1
	return (b, d)
for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	(b, flag) = ([0] * n, True)
	for i in range(n):
		b[a[i] - 1] += 1
		if b[a[i] - 1] == 3:
			flag = False
			print('NO')
			break
	if flag:
		sum = 0
		for i in range(n):
			sum += b[i]
			if not sum <= i + 1:
				flag = False
				print('NO')
				break
		if flag:
			print('YES')
			c = []
			for i in range(n):
				if b[i] == 0:
					c.append(i)
			(b, d) = do(b, c)
			(x, y) = display(a, b, d)
			print(*x)
			print(*y)


t = int(input())
for __ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c = [[] for x in range(n)]
	flag = 0
	for x in range(n):
		c[arr[x] - 1].append(x)
		if len(c[arr[x] - 1]) > 2:
			flag = 1
			break
	a = [-1] * n
	b = [-1] * n
	ae = []
	be = []
	if flag == 1:
		print('NO')
	else:
		for x in range(n - 1, -1, -1):
			if len(c[x]) == 2:
				a[c[x][0]] = x + 1
				ae.append(c[x][1])
				be.append(c[x][0])
				b[c[x][1]] = x + 1
			elif len(c[x]) == 1:
				a[c[x][0]] = x + 1
				b[c[x][0]] = x + 1
			elif len(ae) == 0 or len(be) == 0:
				flag = 1
				break
			else:
				a[ae.pop(-1)] = x + 1
				b[be.pop(-1)] = x + 1
		if flag == 1:
			print('NO')
		else:
			print('YES')
			print(*a)
			print(*b)


import sys
import math
import cmath
import time
for t in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().strip().split()))
	l = [0] * n
	sorter = True
	for i in range(n):
		l[a[i] - 1] += 1
		if l[a[i] - 1] == 3:
			sorter = False
			print('NO')
			break
	if sorter:
		sum = 0
		for i in range(n):
			sum += l[i]
			if not sum <= i + 1:
				sorter = False
				print('NO')
				break
		if sorter:
			print('YES')
			zeros = []
			for i in range(n):
				if l[i] == 0:
					zeros.append(i)
			pq = [0] * n
			count = 0
			for i in range(n):
				if l[i] == 1:
					pq[i] = i + 1
				if l[i] == 2:
					pq[i] = zeros[count] + 1
					pq[zeros[count]] = i + 1
					count += 1
			p = [0] * n
			q = [0] * n
			for i in range(n):
				if l[a[i] - 1] == 1:
					p[i] = a[i]
					q[i] = a[i]
				elif l[a[i] - 1] == 2:
					p[i] = a[i]
					q[i] = pq[a[i] - 1]
					l[a[i] - 1] -= 2
				else:
					p[i] = pq[a[i] - 1]
					q[i] = a[i]
			print(*p)
			print(*q)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = sorted(a)
	d = {}
	(i, f, s, res, pre, c) = (1, [], [], 'YES', b[0], 0)
	for el in b:
		if el == pre:
			c += 1
			if c == 3:
				res = 'NO'
				break
			continue
		if c == 1:
			d[pre] = [pre, 0]
		else:
			while i in d or i == pre:
				i += 1
			if i > pre:
				res = 'NO'
				break
			d[pre] = [i, 2]
			i += 1
		c = 1
		pre = el
	if c == 1:
		d[pre] = [pre, 0]
	else:
		while i in d or i == pre:
			i += 1
		if i > pre:
			res = 'NO'
		d[pre] = [i, 2]
	print(res)
	if res == 'NO':
		continue
	for el in a:
		if d[el][-1] == 0:
			s.append(el)
			f.append(el)
		elif d[el][-1] == 2:
			s.append(el)
			f.append(d[el][0])
			d[el][-1] -= 1
		else:
			s.append(d[el][0])
			f.append(el)
	print(*f, sep=' ')
	print(*s, sep=' ')


import itertools
from collections import defaultdict
from queue import PriorityQueue

def solve(restrictions):
	n = len(restrictions)
	p1 = [-1] * n
	p2 = [-1] * n
	restriction___positions = defaultdict(list)
	for (pos, restriction) in enumerate(restrictions):
		restriction___positions[restriction].append(pos)
	reserved_positions_p1 = []
	reserved_positions_p2 = []
	for restriction in range(n - 1, -1, -1):
		positions = restriction___positions[restriction]
		if len(positions) > 2:
			return False
		elif len(positions) == 2:
			p2[positions[0]] = restriction
			reserved_positions_p1.append(positions[0])
			p1[positions[1]] = restriction
			reserved_positions_p2.append(positions[1])
		elif len(positions) == 1:
			p1[positions[0]] = restriction
			p2[positions[0]] = restriction
		elif len(positions) == 0:
			if len(reserved_positions_p1) == 0:
				return False
			p1_pos = reserved_positions_p1.pop()
			p2_pos = reserved_positions_p2.pop()
			p1[p1_pos] = restriction
			p2[p2_pos] = restriction
	return (p1, p2)

def run():
	n = int(input())
	arr = [int(x) - 1 for x in input().split()]
	ans = solve(arr)
	if ans is False:
		print('NO')
	else:
		(a, b) = ans
		print('YES')
		print(*(x + 1 for x in a))
		print(*(x + 1 for x in b))
tests_nr = int(input())
for _ in range(tests_nr):
	run()


from collections import Counter
import math

def solve(nums):
	og = nums
	p_idx = {}
	q_idx = {}
	nums = sorted(((v, i) for (i, v) in enumerate(nums)))
	for (v, i) in nums:
		if v in p_idx and v in q_idx:
			return ('NO', [], [])
		elif v in p_idx:
			q_idx[v] = i
		else:
			p_idx[v] = i
	fill(p_idx, og)
	fill(q_idx, og)
	p = sorted(p_idx, key=lambda v: p_idx[v])
	q = sorted(q_idx, key=lambda v: q_idx[v])
	e = [max(a, b) for (a, b) in zip(p, q)]
	if e != og:
		return ('NO', [], [])
	return ('YES', p, q)

def fill(p_idx, nums):
	p_idxs = set(p_idx.values())
	idxs_to_fill = [i for i in range(len(nums)) if i not in p_idxs]
	idxs_to_fill.sort(key=lambda i: nums[i])
	num = 1
	for i in idxs_to_fill:
		while num in p_idx:
			num += 1
		p_idx[num] = i
t = int(input())
for _ in range(t):
	_ = input()
	(res, x, y) = solve(list(map(int, input().split())))
	if res == 'NO':
		print(res)
	else:
		print(res)
		print(' '.join(map(str, x)))
		print(' '.join(map(str, y)))


import sys
input = sys.stdin.readline
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [-1] * (2 * n)
	pos = [[] for i in range(n + 1)]
	for i in range(n):
		pos[a[i]].append(i)
	ext = []
	ans = True
	for i in range(n, 0, -1):
		if len(pos[i]) > 2:
			ans = False
			break
		if len(pos[i]) == 0:
			if len(ext) < 2:
				ans = False
				break
			b[ext.pop()] = i
			b[ext.pop()] = i
		elif len(pos[i]) == 1:
			b[pos[i][0]] = i
			b[pos[i][0] + n] = i
		elif len(pos[i]) == 2:
			b[pos[i][0]] = i
			b[pos[i][1] + n] = i
			ext.append(pos[i][0] + n)
			ext.append(pos[i][1])
	if ans:
		print('YES')
		for i in range(0, n):
			print(b[i], end=' ')
		print()
		for i in range(n, 2 * n):
			print(b[i], end=' ')
		print()
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	count = dict()
	flag = 0
	for i in range(n):
		if a[i] not in count:
			count[a[i]] = 1
		else:
			count[a[i]] += 1
			if count[a[i]] == 3:
				flag = 1
				break
	if flag == 1 or n not in count or (1 in count and count[1] == 2):
		print('NO')
	else:
		not_found = []
		for i in range(1, n + 1):
			if i not in count:
				not_found.append(i)
		f = 0
		b = [(j, i) for (i, j) in enumerate(a)]
		b.sort()
		p = [0] * n
		q = [0] * n
		start = 0
		i = 0
		while i < n:
			if count[b[i][0]] == 1:
				p[b[i][1]] = b[i][0]
				q[b[i][1]] = b[i][0]
				i += 1
			else:
				p[b[i][1]] = b[i][0]
				q[b[i + 1][1]] = b[i][0]
				if start == len(not_found) or not_found[start] >= b[i][0]:
					f = 1
					break
				p[b[i + 1][1]] = not_found[start]
				q[b[i][1]] = not_found[start]
				start += 1
				i += 2
		if f == 1:
			print('NO')
		else:
			print('YES')
			print(*p)
			print(*q)


def solve(n, l):
	a = [0 for _ in range(n)]
	b = [0 for _ in range(n)]
	d = [0 for _ in range(n + 1)]
	for i in range(n):
		if d[l[i]] > 1:
			print('NO')
			return
		if d[l[i]] == 0:
			a[i] = l[i]
			d[l[i]] += 1
		else:
			b[i] = l[i]
			d[l[i]] += 1
	t = []
	for i in range(n):
		if a[i] == 0:
			t.append([b[i], i])
	t = sorted(t)[::-1]
	s = set()
	for i in a:
		s.add(i)
	x = n
	for (p, q) in t:
		while x in s:
			x -= 1
		if x > p:
			print('NO')
			return
		a[q] = x
		x -= 1
	t = []
	for i in range(n):
		if b[i] == 0:
			t.append([a[i], i])
	t = sorted(t)[::-1]
	s = set()
	for i in b:
		s.add(i)
	x = n
	for (p, q) in t:
		while x in s:
			x -= 1
		if x > p:
			return 'NO'
			return
		b[q] = x
		x -= 1
	print('YES')
	print(*a)
	print(*b)
	return
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	solve(n, l)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	d = defaultdict(list)
	for (i, ele) in enumerate(arr):
		d[ele].append(i)
	np = []
	for i in range(n):
		if i + 1 not in d:
			np.append(i + 1)
	p = [0] * n
	q = [0] * n
	(s1, s2) = (set(), set())
	poss = True
	for ele in sorted(d.keys()):
		val = d[ele]
		ln = len(val)
		if ln > 2:
			poss = False
			break
		elif ln == 1:
			p[val[0]] = ele
			q[val[0]] = ele
		else:
			p[val[0]] = ele
			q[val[1]] = ele
			if np[0] > ele:
				poss = False
				break
			ele = np.pop(0)
			q[val[0]] = ele
			p[val[1]] = ele
	if poss:
		print('YES')
		for ele in p:
			print(ele, end=' ')
		print()
		for ele in q:
			print(ele, end=' ')
		print()
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	a = [int(s) for s in input().split()]
	for i in range(n):
		a[i] = (a[i], i)
	a.sort()
	ps = set([i + 1 for i in range(n)])
	qs = set([i + 1 for i in range(n)])
	minp = 1
	minq = 1
	p = []
	q = []
	for i in range(n):
		elem = a[i][0]
		if i % 2 == 0:
			if not elem in ps:
				print('NO')
				break
			p.append(elem)
			ps.remove(elem)
			for j in range(minq, n + 1):
				if j in qs:
					minq = j
					break
			if minq > elem:
				print('NO')
				break
			q.append(minq)
			qs.remove(minq)
		else:
			if not elem in qs:
				print('NO')
				break
			q.append(elem)
			qs.remove(elem)
			for j in range(minp, n + 1):
				if j in ps:
					minp = j
					break
			if minp > elem:
				print('NO')
				break
			p.append(minp)
			ps.remove(minp)
	else:
		p_ = [0 for i in range(n)]
		q_ = [0 for i in range(n)]
		for i in range(n):
			p_[a[i][1]] = p[i]
			q_[a[i][1]] = q[i]
		print('YES')
		print(' '.join([str(i) for i in p_]))
		print(' '.join([str(i) for i in q_]))


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = defaultdict(list)
	for (j, i) in enumerate(arr, start=1):
		count[i].append(j)
	if len(max(count.values(), key=len)) > 2 or any((x < i for (i, x) in enumerate(sorted(arr), start=1))):
		print('NO')
	else:
		first = [-1 for _ in range(n + 1)]
		second = list(first)
		(ifirst, isecond) = (list(first), list(first))
		for i in range(n, 0, -1):
			for j in count[i]:
				if ifirst[i] == -1:
					ifirst[i] = j
					first[j] = i
				elif isecond[i] == -1:
					isecond[i] = j
					second[j] = i
		x = int(n)
		vf = int(n)
		vs = int(n)
		while x >= 1:
			for i in count[x]:
				while ifirst[vf] != -1:
					vf -= 1
				while isecond[vs] != -1:
					vs -= 1
				if first[i] == -1 and vf > 0:
					ifirst[vf] = i
					first[i] = vf
				if second[i] == -1 and vs > 0:
					isecond[vs] = i
					second[i] = vs
			x -= 1
		ans = 'YES'
		for i in range(1, n + 1):
			if max(first[i], second[i]) != arr[i - 1]:
				ans = 'NO'
		print(ans)
		if ans == 'YES':
			print(*first[1:])
			print(*second[1:])


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	c = [0] * n
	for i in range(n):
		a[i] -= 1
		c[a[i]] += 1
	if any((c > 2 for c in c)):
		print('NO')
		return
	v = []
	g = [[] for _ in range(n)]
	for i in range(n):
		v += [i] * (2 - c[i])
		for j in range(c[i]):
			if not v:
				print('NO')
				return
			g[i] += (v[-1],)
			g[v[-1]] += (i,)
			v.pop()
	pairs = [[] for _ in range(n)]
	v = [0] * n
	for i in range(n):
		if not v[i]:
			(x, y) = (i, g[i][0])
			while not v[x]:
				v[x] = 1
				pairs[max(x, y)] += ((x + 1, y + 1),)
				(x, y) = (y, x ^ g[y][0] ^ g[y][1])
	print('YES')
	p = [0] * n
	q = [0] * n
	for i in range(n):
		(p[i], q[i]) = pairs[a[i]].pop()
	print(*p)
	print(*q)
for _ in range(int(input())):
	solve()


import heapq
import sys
input = sys.stdin.readline

def readInt():
	return int(input())

def readArr():
	return list(map(int, input().split(' ')))

def makeArr(n):
	return [0] * n

def printArr(arr):
	for x in arr:
		print(x, end=' ')
	print()
T = int(input())
for i in range(T):
	n = readInt()
	arr = readArr()
	p = makeArr(n)
	q = makeArr(n)
	fail = False
	vis = {}
	visP = {}
	visQ = {}
	blankP = []
	blankQ = []
	for (i, x) in enumerate(arr):
		if vis.get(x):
			q[i] = x
			visQ[x] = 1
			heapq.heappush(blankP, (-q[i], i))
		else:
			p[i] = x
			visP[x] = 1
			heapq.heappush(blankQ, (-p[i], i))
		vis[x] = True
	for i in range(n, 0, -1):
		if not visP.get(i):
			if len(blankP) == 0:
				fail = True
				break
			p[heapq.heappop(blankP)[1]] = i
	for i in range(n, 0, -1):
		if not visQ.get(i):
			if len(blankQ) == 0:
				fail = True
				break
			q[heapq.heappop(blankQ)[1]] = i
	for (i, x) in enumerate(arr):
		if max(p[i], q[i]) != x:
			fail = True
	if fail:
		print('NO')
	else:
		print('YES')
		printArr(p)
		printArr(q)


import math
import collections

def func(n, a):
	index = {}
	d = collections.defaultdict(int)
	for i in range(n):
		if index.get(a[i]):
			index[a[i]].append(i)
		else:
			index[a[i]] = [i]
		d[a[i]] += 1
	p = [0 for i in range(n)]
	q = [0 for i in range(n)]
	eisp = []
	eisq = []
	for m in range(n, 0, -1):
		if d[m] == 2:
			p[index[m][0]] = m
			q[index[m][1]] = m
			eisp.append(index[m][1])
			eisq.append(index[m][0])
		if d[m] == 1:
			p[index[m][0]] = m
			eisq.append(index[m][0])
			q[eisq[0]] = m
			eisq.pop(0)
		if d[m] == 0:
			if len(eisp) == 0 or len(eisq) == 0:
				return -1
			p[eisp[0]] = m
			eisp.pop(0)
			q[eisq[0]] = m
			eisq.pop(0)
	if 0 in p or 0 in q:
		return -1
	print('YES')
	print(*p)
	print(*q)
q = int(input())
for i in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	if func(n, a) == -1:
		print('NO')


out = []
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	f = []
	for i in range(n + 1):
		f.append([])
	ans = 'YES'
	for i in range(n):
		f[a[i]].append(i)
		if len(f[a[i]]) > 2:
			ans = 'NO'
	if len(f[-1]) == 0:
		ans = 'NO'
	if ans == 'NO':
		out.append(['NO'])
		continue
	free = []
	p = []
	for i in range(2):
		p.append([0] * n)
	for i in range(n, 0, -1):
		if len(f[i]) == 2:
			k = f[i]
			p[0][k[0]] = i
			p[1][k[1]] = i
			free.append([0, k[1]])
			free.append([1, k[0]])
		elif len(f[i]) == 1:
			k = f[i][0]
			p[0][k] = i
			p[1][k] = i
		elif free:
			for j in range(2):
				k = free.pop(0)
				p[k[0]][k[1]] = i
		else:
			ans = 'NO'
	out.append([ans])
	if ans == 'YES':
		out.append(p[0])
		out.append(p[1])
for i in out:
	print(*i)