Задан массив \(a\), состоящий из \(n\) целых чисел.
Каждая позиция массива \(i\) (\(1 \le i \le n\)) либо заблокирована, либо разблокирована. Разрешается взять все значения на разблокированных позициях, переупорядочить их произвольным образом и вернуть их на разблокированные позиции. Не разрешается удалять значения, добавлять новые или переупорядочивать значения на заблокированных позициях.
Например, если \(a = [-1, 1, \underline{3}, 2, \underline{-2}, 1, -4, \underline{0}]\), подчеркнутые позиции заблокированы. Можно получить следующие массивы:
- \([-1, 1, \underline{3}, 2, \underline{-2}, 1, -4, \underline{0}]\);
- \([-4, -1, \underline{3}, 2, \underline{-2}, 1, 1, \underline{0}]\);
- \([1, -1, \underline{3}, 2, \underline{-2}, 1, -4, \underline{0}]\);
- \([1, 2, \underline{3}, -1, \underline{-2}, -4, 1, \underline{0}]\);
- и некоторые другие.
Пусть \(p\) будет последовательностью префиксных сумм массива \(a\) после переупорядочения. То есть \(p_1 = a_1\), \(p_2 = a_1 + a_2\), \(p_3 = a_1 + a_2 + a_3\), \(\dots\), \(p_n = a_1 + a_2 + \dots + a_n\).
Пусть \(k\) будет максимальным \(j\) (\(1 \le j \le n\)) таким, что \(p_j < 0\). Если нет таких \(j\), что \(p_j < 0\), то \(k = 0\).
Ваша цель — переупорядочить значения таким образом, чтобы \(k\) было минимально возможным.
Выведите массив \(a\) после переупорядочения такой, что значение \(k\) для него минимально возможно. Если существует несколько ответов, то выведите любой из них.
Выходные данные
Выведите \(n\) целых чисел — массив \(a\) после переупорядочения. Значение \(k\) (максимальное такое \(j\), что \(p_j < 0\) (или \(0\), если таких \(j\) нет)) должно быть минимально возможно. Для каждой заблокированной позиции выведенное число должно совпадать с начальным. Значения на всех разблокированных позициях должны быть перестановкой начальных значений.
Если существует несколько ответов, то выведите любой из них.
Примечание
В первом наборе входных данных можно переставить все значения как угодно, но любое переупорядочение приведет к \(k = 0\). Например, для переупорядочения \([1, 2, 3]\), \(p=[1, 3, 6]\), поэтому нет такого \(j\), что \(p_j < 0\). Таким образом, \(k = 0\).
Во втором наборе не разрешается переупорядочивать элементы вообще. Поэтому массив в выводе должен совпадать с данным массивом.
В третьем наборе префиксные суммы в выведенном массиве равны \(p = [-8, -14, -13, -9, -5, 2, 0]\). Максимальное \(j\) равно \(5\), поэтому \(k = 5\). Невозможно переупорядочить так, чтобы было \(k < 5\).
В четвертом наборе \(p = [-4, -4, -3, 3, 6]\).
В пятом наборе \(p = [-1, 3, 10, 2, 12, 11]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 3 2
0 0 0
4
2 -3 4 -1
1 1 1 1
7
-8 4 -2 -6 4 7 1
1 0 0 0 1 1 0
5
0 1 -4 6 3
0 0 0 1 1
6
-1 7 10 4 -8 -1
1 0 0 0 0 1
|
1 2 3
2 -3 4 -1
-8 -6 1 4 4 7 -2
-4 0 1 6 3
-1 4 7 -8 10 -1
|