У вас есть последовательность \(a\) из \(n\) элементов \(1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k)\) (\(k \le n < 2k\)).
Назовем инверсией в \(a\) пару индексов \(i < j\) таких, что \(a[i] > a[j]\).
Предположим, что у вас есть некоторая перестановка \(p\) размера \(k\) и вы строите последовательность \(b\) размера \(n\) следующим образом: \(b[i] = p[a[i]]\).
Ваша задача — найти такую перестановку \(p\), что суммарное количество инверсий в \(b\) не превосходит суммарного количества инверсий в \(a\), и \(b\) лексикографически максимальна.
Напоминание: последовательность из \(k\) целых чисел называется перестановкой, если она содержит все числа от \(1\) по \(k\) ровно по одному разу.
Еще одно напоминание: последовательность \(s\) лексикографически меньше последовательности \(t\), если либо \(s\) — префикс \(t\), или для первого \(i\), для которого \(s_i \ne t_i\), выполняется \(s_i < t_i\) (в первой позиции, в которой эти последовательности различаются, элемент в \(s\) меньше элемента в \(t\)).
Выходные данные
Для каждого набора входных данных, выведите \(k\) целых чисел — перестановку \(p\), которая максимизирует \(b\) лексикографически, не увеличивая суммарное количество инверсий.
Можно доказать, что \(p\) существует и единственная.
Примечание
В первом наборе входных данных, последовательность \(a = [1]\), поэтому существует только одна перестановка \(p = [1]\).
Во втором наборе, последовательность \(a = [1, 2]\). В \(a\) нет инверсий, а потому только одна перестановка \(p = [1, 2]\) не увеличивает количество инверсий.
В третьем наборе, \(a = [1, 2, 1]\) и имеет \(1\) инверсию. Если мы используем \(p = [2, 1]\), то \(b = [p[a[1]], p[a[2]], p[a[3]]] = [2, 1, 2]\) и также имеет \(1\) инверсию.
В четвертом наборе, \(a = [1, 2, 3, 2]\), и так как \(p = [1, 3, 2]\) то \(b = [1, 3, 2, 3]\). И \(a\), и \(b\) имеют по \(1\) инверсии и \(b\) — лексикографически максимальна.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1
2 2
3 2
4 3
|
1
1 2
2 1
1 3 2
|