← 返回题目列表

Codeforces · 1998/B

B. 最小化等和子数组

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

给你一个长度为 $$$n$$$ 的排列$$$^{\text{*}}$$$ $$$p$$$。

找到长度为 $$$n$$$ 的排列 $$$q$$$,使 ($$$i, j$$$) ($$$1 \leq i \leq j \leq n$$$) 的数量最小化,使得 $$$p_i + p_{i+1} + \ldots + p_j = q_i + q_{i+1} + \ldots + q_j$$$。

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)。

以下行包含 $$$n$$$ 空格分隔的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — 表示长度 $$$n$$$ 的排列 $$$p$$$。

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

输出

对于每个测试用例,输出一行包含长度 $$$n$$$ 的任意排列(排列 $$$q$$$),使得 $$$q$$$ 最小化对的数量。

示例

输入 #1

3
2
1 2
5
1 2 3 4 5
7
4 7 5 1 2 6 3

输出 #1

2 1
3 5 4 2 1
6 2 1 4 7 3 5

注意

对于第一个测试,仅存在一对 ($$$i, j$$$) ($$$1 \leq i \leq j \leq n$$$) 使得 $$$p_i + p_{i+1} + \ldots + p_j = q_i + q_{i+1} + \ldots + q_j$$$,即 ($$$1, 2$$$)。可以证明,不存在这样的没有对的 $$$q$$$ 。