← 返回题目列表

Codeforces · 2131/B

B. 交替系列

中文机器翻译题面 查看原题

给你一个整数$$$n$$$。调用长度为 $$$n$$$ 的数组 $$$a$$$ 好 如果:

  • 对于所有 $$$1 \le i \lt n$$$,$$$a_i \cdot a_{i+1} \lt 0$$$ (即相邻元素的乘积为负)。
  • 对于长度至少为$$$2$$$的所有子数组$$$^{\text{∗}}$$$,子数组中所有元素的总和为正$$$^{\text{†}}$$$。

另外,我们说一个长度为 $$$n$$$ 的好数组 $$$a$$$ 是 更好 比另一个长度为 $$$n$$$ 的好的数组 $$$b$$$ 如果 $$$[|a_1|, |a_2|, \ldots, |a_n|]$$$ 按字典顺序小于 $$$[|b_1|, |b_2|, \ldots, |b_n|]$$$ $$$^{\text{‡}}$$$。注意$$$|z|$$$表示整数$$$z$$$的绝对值。

输出一个长度为 $$$n$$$ 的良好数组,使其优于长度为 $$$n$$$ 的所有其他良好数组。

$$$^{\text{*}}$$$数组 $$$c$$$ 是数组 $$$d$$$ 的子数组,如果 $$$c$$$ 可以通过从 $$$d$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

$$$^{\text{†}}$$$如果 $$$x \gt 0$$$,则整数 $$$x$$$ 为正。

$$$^{\text{‡}}$$$当且仅当满足以下条件之一时,序列 $$$a$$$ 按字典顺序小于序列 $$$b$$$:

  • $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;或
  • 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,序列 $$$a$$$ 的元素比 $$$b$$$ 中的相应元素小。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。

每个测试用例的一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 数组的长度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$),即新行上的数组元素。

示例

输入
复制

2
2
3

输出
复制

-1 2
-1 3 -1

注意

在第一个测试用例中,因为 $$$a_1 \cdot a_2 = -2 \lt 0$$$ 和 $$$a_1 + a_2 = 1 \gt 0$$$,它满足两个约束。另外可以证明对应的$$$b = [1, 2]$$$为 更好 比任何其他 好 长度为 $$$2$$$ 的数组。