Вам дана перестановка \(p\) длины \(n\), а также целое неотрицательное число \(k\). Вам нужно построить перестановку \(q\) длины \(n\) такую, что \(\operatorname{inv}(q) + \operatorname{inv}(q \cdot p) = k {}^\dagger {}^\ddagger\), или определить, что это сделать невозможно.
\({}^\dagger\) Для двух перестановок \(p\) и \(q\) одинаковой длины \(n\) перестановка \(w = q \cdot p\) такова, что \(w_i = q_{p_i}\) для всех \(1 \le i \le n\).
\({}^\ddagger\) Для перестановки \(p\) длины \(n\) функция \(\operatorname{inv}(p)\) возвращает количество инверсий \(p\), то есть количество пар индексов \(1 \le i < j \le n\) таких, что \(p_i > p_j\).
Выходные данные
Для каждого набора входных данных выведите в отдельной строке «YES», если существует перестановка \(q\), удовлетворяющая заданному условию, или «NO», если такой перестановки не существует.
Если ответ «YES», то во второй строке выведите \(n\) целых чисел \(q_1, q_2, \ldots, q_n\), которые представляют собой удовлетворяющую условию перестановку \(q\). Если таких \(q\) несколько, выведите любую из них.
Примечание
В первом наборе входных данных имеем \(q \cdot p = [2, 1, 3]\), \(\operatorname{inv}(q) = 3\), и \(\operatorname{inv}(q \cdot p) = 1\).
В четвертом наборе входных данных имеем \(q \cdot p = [9, 1, 8, 5, 7, 6, 4, 3, 2]\), \(\operatorname{inv}(q) = 24\), и \(\operatorname{inv}(q \cdot p) = 27\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 4
2 3 1
5 5
2 3 5 1 4
6 11
5 1 2 3 4 6
9 51
3 1 4 2 5 6 7 8 9
1 0
1
|
YES
3 2 1
NO
NO
YES
1 5 9 8 7 6 4 3 2
YES
1
|