Единственное отличие между этой задачей и простой версией — в ограничениях на \(t\) и \(n\).
Вам дан массив из \(n\) положительных целых чисел \(a_1,\dots,a_n\), а также целое (возможно, отрицательное) число \(c\).
Среди всех возможных перестановок \(b_1,\dots,b_n\) массива \(a_1,\dots,a_n\), рассмотрим минимально возможное значение \(\)\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|.\(\) Найдите лексикографически наименьшую перестановку \(b\) массива \(a\), на которой достигается этот минимум.
Последовательность \(x\) лексикографически меньше последовательности \(y\), если и только если выполняется один из следующих пунктов:
- \(x\) — префикс \(y\), но \(x \ne y\);
- в первой позиции, где \(x\) и \(y\) различны, в последовательности \(x\) находится элемент, меньший соответствующего элемента \(y\).
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел \(b_1,\dots,b_n\), задающих лексикографически наименьшую перестановку \(a\), на которой достигается минимум \(\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|\).
Примечание
В первом наборе входных данных можно доказать, что минимальное значение \(\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|\) равно \(27\), а перестановка \(b = [9,3,1,4,5,1]\) является лексикографически наименьшей перестановкой \(a\), на которой достигается этот минимум: \(|3-9-(-7)|+|1-3-(-7)|+|4-1-(-7)|+|5-4-(-7)|+|1-5-(-7)| = 1+5+10+8+3 = 27\).
Во втором наборе входных данных минимально возможное значение \(\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|\) равно \(0\), при этом \(b = [1,3,5]\) является лексикографически наименьшей перестановкой \(a\), на которой достигается этот минимум.
В третьем наборе входных данных существует всего одна перестановка \(b\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 -7
3 1 4 1 5 9
3 2
1 3 5
1 2718
2818
|
9 3 1 4 5 1
1 3 5
2818
|