CF1375A Sign Flipping

给定 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $n$ 是奇数。你可以选择将其中一些（可以全部或一个也不选）数的符号翻转。你需要进行符号翻转，使得满足以下两个条件： 1. 至少有 $\frac{n - 1}{2}$ 个相邻差值 $a_{i + 1} - a_i$（$i = 1, 2, \dots, n - 1$）大于等于 $0$。 2. 至少有 $\frac{n - 1}{2}$ 个相邻差值 $a_{i + 1} - a_i$（$i = 1, 2, \dots, n - 1$）小于等于 $0$。 请找出任意一种合法的符号翻转方案。可以证明，在给定的限制条件下，至少存在一种满足要求的符号翻转方案。如果有多种方案，你可以输出任意一种。

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试数据组数。 每组测试数据的第一行包含一个整数 $n$（$3 \le n \le 99$，$n$ 为奇数），表示给定的整数个数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \le a_i \le 10^9$），表示这些整数。 保证所有测试数据中 $n$ 的总和不超过 $10000$。

对于每组测试数据，输出 $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$ 是非正数。 由 ChatGPT 4.1 翻译