Problem Description

有 $n$ 个平台，每个平台的高度 $h$ 在 $[1,n]$ 之内。每个平台上都有一枚金币，只要到达这个平台就能获得这枚金币，离开平台时，平台便会消失。Hubery 迫切地想要得到这些金币，因此他决定经过所有的平台来得到这些金币。

这些平台具有一个奇怪的规则：每两次连续的跳跃方向必须相反，且高度相同的平台间并不能相互跳跃。即，令第 $i$ 次抵达的平台为 $x_i$ ，则需保证：

• $h_{x_i} \neq h_{x_{i-1}}$；


• 若 $h_{x_{i}}\gt h_{x_{i-1}}$，那么必须有 $h_{x_{i+1}}\lt h_{x_{i}}$；


• 若 $h_{x_{i}}\lt h_{x_{i-1}}$，那么必须有 $h_{x_{i+1}}\gt h_{x_{i}}$。

在满足以上规则的前提下，可以从一个平台跳到任意一个未经过的平台。如果不按照给定规则进行跳跃，那么所有的金币（包括已收集的）都会消失。Hubery 可以任意选择一个平台作为起始平台。如果存在某个平台无论如何都不能到达，他将会放弃此次行动。

Hubery 最近学业压力很重，因而他希望你来帮他决定每一次到达的平台编号 $x_i$。如果存在多组方案，Hubery 认为字典序最小的跳跃方案是最优的。请帮助 Hubery 找到最优的跳跃方案，如果他不得不放弃此次行动，请输出 $-1$。

若 $x^a_1,x^a_2,\ldots ,x^a_n$ 和 $x^b_1,x^b_2,\ldots ,x^b_n$ 是两组合法的跳跃方案，若对 $\forall i\in[1,m)$，有 $x^a_i=x^b_i$，且 $x^a_m\lt x^b_m$，那么前者字典序更小，是更优的解决方案。

Input

第一行输入一个正整数 $T$（$1 \leq T \leq 20$），表示测试数据组数。

对于每组数据，第一行输入一个正整数 $n$（$3 \leq n \leq 5000$），表示平台的个数。

第二行输入 $n$ 个正整数 $h_i$（$1 \leq h_i \leq n$），表示第 $i$ 个平台的高度。

保证各组数据 $n$ 的总和最多为 $50000$。

Output

对于每组数据，若存在合法跳跃方案，输出 $n$ 个正整数 $x_i$（$1 \leq x_i \leq n$）表示第 $i$ 次经过的平台。否则，输出 $-1$。

请勿输出行末空格。

3
3
1 2 3
3
2 1 1
3
2 2 2

1 3 2
2 1 3
-1