Даны \(n\) массивов \(a_1\), \(\ldots\), \(a_n\). Длина каждого массива равна двум. Таким образом, \(a_i = [a_{i, 1}, a_{i, 2}]\). Вам надо склеить массивы в один массив длины \(2n\) так, чтобы количество инверсий\(^{\dagger}\) в получившемся массиве было как можно меньше. Обратите внимание, что вам не нужно считать само количество инверсий.
Более формально, вам надо выбрать перестановку\(^{\ddagger}\) \(p\) длины \(n\), чтобы массив \(b = [a_{p_1,1}, a_{p_1,2}, a_{p_2, 1}, a_{p_2, 2}, \ldots, a_{p_n,1}, a_{p_n,2}]\) содержал как можно меньше инверсий.
\(^{\dagger}\)Количество инверсий в массиве \(c\) — это количество пар индексов \(i\) и \(j\), таких что \(i < j\) и \(c_i > c_j\).
\(^{\ddagger}\)Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите \(2n\) целых чисел — элементы полученного вами массива. Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных мы склеили массивы в порядке \(2, 1\). Рассмотрим инверсии в полученном массиве \(b = [2, 3, 1, 4]\):
- \(i = 1\), \(j = 3\), так как \(b_1 = 2 > 1 = b_3\);
- \(i = 2\), \(j = 3\), так как \(b_2 = 3 > 1 = b_3\).
Таким образом, количество инверсий равно \(2\). Можно доказать, что это минимально возможное количество инверсий.
Во втором наборе входных данных мы склеили массивы в порядке \(3, 1, 2\). Рассмотрим инверсии в полученном массиве \(b = [2, 1, 3, 2, 4, 3]\):
- \(i = 1\), \(j = 2\), так как \(b_1 = 2 > 1 = b_2\);
- \(i = 3\), \(j = 4\), так как \(b_3 = 3 > 2 = b_4\);
- \(i = 5\), \(j = 6\), так как \(b_5 = 4 > 3 = b_6\).
Таким образом, количество инверсий равно \(3\). Можно доказать, что это минимально возможное количество инверсий.
В третьем наборе входных данных мы склеили массивы в порядке \(4, 2, 1, 5, 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 4
2 3
3
3 2
4 3
2 1
5
5 10
2 3
9 6
4 1
8 7
1
10 20
|
2 3 1 4
2 1 3 2 4 3
4 1 2 3 5 10 8 7 9 6
10 20
|