Горилла и Noobish_Monk нашли три числа \(n\), \(m\) и \(k\) (\(m < k\)). Они решили построить перестановку\(^{\dagger}\) длины \(n\).
Для перестановки Noobish_Monk придумал следующую функцию: \(g(i)\) равно сумме всех чисел перестановки на префиксе длины \(i\), не больших \(m\). Аналогично, Горилла придумал функцию \(f\), \(f(i)\) равно сумме всех чисел перестановки на префиксе длины \(i\), не меньшие \(k\). Префиксом длины \(i\) называется массив, состоящий из первых \(i\) элементов исходного.
Например, если \(n = 5\), \(m = 2\), \(k = 5\), а перестановка равна \([5, 3, 4, 1, 2]\), то:
- \(f(1) = 5\), так как \(5 \ge 5\); \(g(1) = 0\), так как \(5 > 2\);
- \(f(2) = 5\), так как \(3 < 5\); \(g(2) = 0\), так как \(3 > 2\);
- \(f(3) = 5\), так как \(4 < 5\); \(g(3) = 0\), так как \(4 > 2\);
- \(f(4) = 5\), так как \(1 < 5\); \(g(4) = 1\), так как \(1 \le 2\);
- \(f(5) = 5\), так как \(2 < 5\); \(g(5) = 1 + 2 = 3\), так как \(2 \le 2\).
Помогите им найти такую перестановку, для которой значение \(\left(\sum_{i=1}^n f(i) - \sum_{i=1}^n g(i)\right)\) будет максимально.
\(^{\dagger}\)Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите перестановку — набор чисел, который удовлетворяет условиям задачи. Если существует несколько решений, выведите любое из них.