Вам дан массив целых чисел \(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\)).
Выходные данные
Для каждого набора входных данных, если не существует \(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» будут распознаны как положительный ответ).
Примечание
В первом наборе входных данных \(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\) не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|