题目描述

最小化相等和子数组

已知 农夫约翰喜欢排列，我也喜欢它们！

给定一个长度为 $n$ 的排列 $p$。

找到一个长度为 $n$ 的排列 $q$，使得以下条件下的对数最小化：对所有 $1 \leq i \leq j \leq n$，使得 $p_i + p_{i+1} + \ldots + p_j = q_i + q_{i+1} + \ldots + q_j$。

注：一个长度为 $n$ 的排列是一个包含 $1$ 到 $n$ 的 $n$ 个不同整数的数组。例如，[2, 3, 1, 5, 4] 是一个排列，但 [1, 2, 2] 不是一个排列（数字 2 在数组中出现了两次），而 [1, 3, 4] 也不是一个排列（$n=3$，但数组中有 4）。

输入格式

第一行包含一个整数 $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$ 最小化满足条件的对数。

说明/提示

对于第一个测试用例，存在唯一一对 $(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$ 使得不存在满足条件的对。

样例

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

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