C. Поэлементное ограничение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел $$$a$$$ длины $$$n$$$.

Найдите две перестановки$$$^\dagger$$$ $$$p$$$ и $$$q$$$ длины $$$n$$$ такие, что $$$\max(p_i,q_i)=a_i$$$ для всех $$$1 \leq i \leq n$$$ или сообщите, что таких $$$p$$$ и $$$q$$$ не существует.

$$$^\dagger$$$ Перестановкой длины $$$n$$$ называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ тоже не является перестановкой ($$$n=3$$$, но в массиве присутствует $$$4$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина перестановки.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных, если не существует $$$p$$$ и $$$q$$$, удовлетворяющих условиям, выведите «NO» (без кавычек).

В противном случае выведите «YES» (без кавычек), затем выведите $$$2$$$ строки. Первая строка должна содержать $$$n$$$ целых $$$p_1,p_2,\ldots,p_n$$$, а вторая строка должна содержать $$$n$$$ целых $$$q_1,q_2,\ldots,q_n$$$.

Если существует несколько решений, вы можете вывести любое из них.

Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes» и «Yes» будут распознаны как положительный ответ).

Пример
Входные данные
3
1
1
5
5 3 4 2 5
2
1 1
Выходные данные
YES
1 
1 
YES
1 3 4 2 5 
5 2 3 1 4 
NO
Примечание

В первом наборе входных данных $$$p=q=[1]$$$. Это верно, так как $$$a_1 = max(p_1,q_1) = 1$$$.

Во втором наборе $$$p=[1,3,4,2,5]$$$ и $$$q=[5,2,3,1,4]$$$. Эти массивы удовлетворяют условию, так как:

  • $$$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$$$.

В третьем наборе можно показать, что таких $$$p$$$ и $$$q$$$ не существует.