← 返回题目列表

Codeforces · 1431/D

D. 使用过的标记

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

你们大学有一个大礼堂,今天你在那里值班。今天将会有 $$$n$$$ 讲座 — 全部来自不同的讲师,您当前的任务是选择它们发生的顺序 $$$or$$$。

每位讲师在讲座期间都会使用一支记号笔在黑板上写一些东西。不幸的是,你使用的标记越多,标记就会变得越差,讲师可能会拒绝使用在他们看来变得太糟糕的标记。

正式来说,第 $$$i$$$ 讲师的接受值是 $$$a_i$$$,这意味着他们不会使用至少在 $$$a_i$$$ 讲座中已经使用过的标记,并将要求更换。更具体地说:

- 在第一堂课之前,您在礼堂中放置了一个新标记;
- 在第 $$$ord_j$$$ 位讲师(按您选择的顺序)开始之前,他们会检查标记的质量,如果之前至少在 $$$a_{ord_j}$$$ 讲座中使用过,他们会要求您提供新的标记;
- 如果你被要求提供一个新的记号笔,那么你扔掉旧的记号笔,在礼堂里放置一个新的记号笔,然后讲师进行演讲。

您知道:标记越好 — 观众就越容易理解讲师所写的内容,因此您希望最大限度地增加所用标记的数量。不幸的是,上级密切关注花费了多少标记,所以你不能在每次讲座之前更换标记。因此,只有当讲师要求时,您才必须更换标记。如果至少一名讲师在演讲中使用了该标记,则该标记被视为已使用。

您可以选择讲师授课的顺序$$$或$$$。找到导致所使用标记的最大可能数量的顺序。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 独立测试的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 500$$$) — 讲座和讲师的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) - 每个讲师的接受值。

输出

对于每个测试用例,打印 $$$n$$$ 个整数 — 讲师的 $$$ord$$$ 顺序,使使用的标记数量最大化。讲师按输入顺序从 $$$1$$$ 到 $$$n$$$ 编号。如果有多个答案,请打印其中任何一个。

示例

输入 #1

4
4
1 2 1 2
2
2 1
3
1 1 1
4
2 3 1 3

输出 #1

4 1 3 2
1 2
3 1 2
4 3 2 1

注意

在第一个测试用例中,最佳顺序之一如下:

1. 第 $$$4$$$ 位讲师排在第一位。标记是新的,所以他们不会要求更换;
2. 接下来是$$$1$$$-st 讲师。该标记仅使用一次,由于 $$$a_1 = 1$$$,讲师要求更换;
3. 接下来是$$$3$$$-rd 讲师。第二个标记仅使用一次,由于 $$$a_3 = 1$$$,讲师要求更换;
4. $$$2$$$-nd 讲师排在最后。第三个标记仅使用一次,但 $$$a_2 = 2$$$,因此讲师使用此标记。

在第二个测试用例中,使用了 $$$2$$$ 标记。

在第三个测试用例中,使用了 $$$3$$$ 标记。

在第四个测试用例中,使用了 $$$3$$$ 标记。