一个班的学生厌倦了每天穿同一双鞋,所以他们决定互相洗牌。在这个问题中,一双鞋是不可分割的,被视为一个单一的物体。
班级中有 $$$n$$$ 个学生,并且给你一个非降序数组 $$$s$$$,其中 $$$s_i$$$ 是第 $$$i$$$ 个学生的鞋码。只有当没有学生得到自己的鞋子并且每个学生得到的鞋子尺寸大于或等于他们的尺码时,洗牌鞋子才有效。
您必须输出 $$$\{1,2,\ldots,n\}$$$ 的排列 $$$p$$$ 表示有效的鞋子洗牌,其中第 $$$i$$$ 学生获得第 $$$p_i$$$ 学生的鞋子 ($$$p_i \ne i$$$)。如果不存在有效的洗牌,则输出 $$$-1$$$。
排列是由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数组成的数组,按任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq10^5$$$) — 学生人数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$s_1, s_2,\ldots,s_n$$$ ($$$1\leq s_i\leq10^9$$$, 以及对于所有 $$$1\le i<n$$$, $$$s_i\le s_{i+1}$$$) — 鞋码学生。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,使用以下格式在一行中打印答案。
如果不存在有效的洗牌,则打印数字 $$$-1$$$ 作为答案。
如果存在有效的洗牌,则打印 $$$n$$$ 空格分隔的整数 - $$$p$$$ 的排列 $$$1,2,\ldots,n$$$ 表示有效的洗牌,其中第 $$$i$$$ 个学生获得第 $$$p_i$$$ 个学生的鞋子。如果有多个答案,则打印其中任何一个。
示例
输入 #1
2 5 1 1 1 1 1 6 3 6 8 13 15 21
输出 #1
5 1 2 3 4 -1
注意
在第一个测试用例中,$$$1,\ldots,n$$$ 的任何排列 $$$p$$$ 都表示有效的洗牌,因为所有学生都有相同的鞋码,因此任何人都可以穿任何人的鞋子。
在第二个测试用例中,可以表明不可能进行有效的洗牌。