Вам дан массив \(a\) из \(2n\) различных целых чисел. Вы хотите расположить элементы этого массива по кругу так, чтобы ни один элемент не был равен среднему арифметическому своих \(2\) соседей.
Более формально, найдите массив \(b\) такой, что:
\(b\) является перестановкой \(a\).
Для каждого \(i\) от \(1\) до \(2n\), \(b_i \neq \frac{b_{i-1}+b_{i+1}}{2}\), где \(b_0 = b_{2n}\) и \(b_{2n+1} = b_1\).
Можно показать, что при ограничениях задачи такой массив \(b\) всегда существует.
Выходные данные
Для каждого набора входных данных выведите \(2n\) целых чисел, \(b_1, b_2, \ldots b_{2n}\), для которых выполняются требования из условия.
Примечание
В первом примере массив \([3, 1, 4, 2, 5, 6]\) подходит, так как он является перестановкой \([1, 2, 3, 4, 5, 6]\), а также \(\frac{3+4}{2}\neq 1\), \(\frac{1+2}{2}\neq 4\), \(\frac{4+5}{2}\neq 2\), \(\frac{2+6}{2}\neq 5\), \(\frac{5+3}{2}\neq 6\), \(\frac{6+1}{2}\neq 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 2 3 4 5 6
2
123 456 789 10
1
6 9
|
3 1 4 2 5 6
123 10 456 789
9 6
|