Вам даны \(n\) целых чисел \(a_1, a_2, \dots, a_n\), где \(n\) нечетно. Вы можете поменять знаки некоторых (возможно, всех или ни одного) из них. Вы хотите поменять знаки таким образом, чтобы выполнялись следующие условия:
- Не менее \(\frac{n - 1}{2}\) среди разностей соседних \(a_{i + 1} - a_i\) для \(i = 1, 2, \dots, n - 1\) больше либо равны \(0\).
- Не менее \(\frac{n - 1}{2}\) среди разностей соседних \(a_{i + 1} - a_i\) для \(i = 1, 2, \dots, n - 1\) меньше либо равны \(0\).
Найдите любой подходящий способ поменять знаки. Можно показать, что при данных ограничениях всегда существует хотя бы один выбор знаков, который удовлетворяет требуемому условию. Если существует несколько решений, выведите любое из них.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел \(b_1, b_2, \dots, b_n\), соответствующих целым числам после изменения знаков. \(b_i\) должно быть равно либо \(a_i\), либо \(-a_i\), а также среди разностей соседних \(b_{i + 1} - b_i\) для \(i = 1, \dots, n - 1\), по крайней мере \(\frac{n - 1}{2}\) должна быть неотрицательными, и хотя бы \(\frac{n - 1}{2}\) должна быть неположительными.
Можно показать, что при данных ограничениях всегда существует хотя бы один выбор знаков, который удовлетворяет требуемому условию. Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных разница \((-4) - (-2) = -2\) неположительна, а разница \(3 - (-4) = 7\) неотрицательна.
Во втором наборе входных данных нам не нужно менять знаки. Все \(4\) разности равны \(0\), и являются как неположительными, так и неотрицательными.
В третьем наборе входных данных \(7 - (-4)\) и \(4 - (-6)\) неотрицательны, а \((-4) - (-2)\) и \((-6) - 7\) неположительны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
-2 4 3
5
1 1 1 1 1
5
-2 4 7 -6 4
9
9 7 -4 -2 1 -3 9 -4 -5
9
-4 1 9 4 8 9 5 1 -9
|
-2 -4 3
1 1 1 1 1
-2 -4 7 -6 4
-9 -7 -4 2 1 -3 -9 -4 -5
4 -1 -9 -4 -8 -9 -5 -1 9
|