在下一种情况下,我们调用一个由值 $$$v$$$ 主导的数组 $$$t$$$ 。
首先,数组 $$$t$$$ 应该至少有 $$$2$$$ 元素。现在,我们计算 $$$t$$$ 中每个数字 $$$num$$$ 出现的次数,并将其定义为 $$$occ(num)$$$。那么 $$$t$$$ 占主导地位(由 $$$v$$$)当且仅当 $$$occ(v) > occ(v')$$$ 对于任何其他数字 $$$v'$$$。例如,数组 $$$[1, 2, 3, 4, 5, 2]$$$、$$$[11, 11]$$$ 和 $$$[3, 2, 3, 2, 3]$$$ 占主导地位(分别由 $$$2$$$、$$$11$$$ 和 $$$3$$$ 主导),但数组 $$$[3]$$$, $$$[1, 2]$$$ 和 $$$[3, 3, 2, 2, 1]$$$ 不是。
小提示:由于任何数组只能由一个数字支配,因此我们不能指定这个数字,而只能说该数组要么受支配,要么不受支配。
给定数组 $$$a_1, a_2, \dots, a_n$$$。计算它的最短支配子数组或者说不存在这样的子数组。
$$$a$$$ 的子数组是数组 $$$a$$$ 的连续部分,i。 e.数组 $$$a_i, a_{i + 1}, \dots, a_j$$$ 对于某些 $$$1 \le i \le j \le n$$$。
输入
第一行包含单个整数 $$$T$$$ ($$$1 \le T \le 1000$$$) — 测试用例的数量。每个测试用例由两行组成。
第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组 $$$a$$$ 的对应值。
保证一次测试中所有数组的总长度不超过$$$2 \cdot 10^5$$$。
输出
打印 $$$T$$$ 整数 — 每个测试用例一个。对于每个测试用例,打印唯一的整数 - 最短主导子数组的长度,如果没有这样的子数组,则打印 $$$-1$$$ 。
示例
输入 #1
4 1 1 6 1 2 3 4 5 1 9 4 1 2 4 5 4 3 2 1 4 3 3 3 3
输出 #1
-1 6 3 2
注意
在第一个测试用例中,不存在长度至少为 $$$2$$$ 的子数组,因此答案为 $$$-1$$$。
在第二个测试用例中,整个数组受支配(由 $$$1$$$ 支配),并且它是唯一受支配的子数组。
在第三个测试用例中,子数组 $$$a_4, a_5, a_6$$$ 是最短支配子数组。
在第四个测试用例中,所有长度大于 1 的子数组都占主导地位。