← 返回题目列表

Codeforces · 1867/A

A. green_gold_dog,数组和排列

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

green_gold_dog 有一个长度为 $$$n$$$ 的数组 $$$a$$$,他想要找到一个长度为 $$$n$$$ 的排列 $$$b$$$,使得数组 $$$a$$$ 和排列 $$$b$$$ 之间的元素差异中不同数字的数量最大化。

长度 $$$n$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 可以任意顺序。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列(因为 $$$2$$$ 在数组中出现两次),并且 $$$[1,3,4]$$$ 也不是排列(因为 $$$n=3$$$,但 $$$4$$$ 在数组中出现)。

长度为 $$$n$$$ 的两个数组 $$$a$$$ 和 $$$b$$$ 之间的元素差异是长度为 $$$n$$$ 的数组 $$$c$$$,其中 $$$c_i$$$ = $$$a_i - b_i$$$ ($$$1 \leq i \leq n$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 4 \cdot 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4 \cdot 10^4$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

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

输出

对于每个测试用例,输出 $$$n$$$ 数字 - 合适的排列 $$$b$$$。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3
1
100000
2
1 1
3
10 3 3

输出 #1

1 
2 1 
1 3 2

注意

在第一组输入数据中,数组的元素差异为[99999]。这里,有一个不同的数字,很明显,在长度为 1 的数组中,不能有多个不同的元素。

在第二组输入数据中,数组的逐元素差异为 [-1, 0]。这里有两个不同的数字,显然在长度为 2 的数组中,不能有超过两个不同的元素。

在第三组输入数据中,数组的元素差异为 [9, 0, 1]。这里有三个不同的数字,显然在长度为三的数组中,不同的元素不能超过三个。