Doremy 有 $$$n$$$ 桶油漆,由长度为 $$$n$$$ 的数组 $$$a$$$ 表示。桶$$$i$$$包含颜色为$$$a_i$$$的油漆。
设 $$$c(l,r)$$$ 为子数组 $$$[a_l,a_{l+1},\ldots,a_r]$$$ 中不同元素的数量。选择 $$$2$$$ 整数 $$$l$$$ 和 $$$r$$$ 使得 $$$l \leq r$$$ 和 $$$r-l-c(l,r)$$$ 最大化。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$)。
保证$$$n$$$的总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出 $$$l$$$ 和 $$$r$$$ 使得 $$$l \leq r$$$ 和 $$$r-l-c(l,r)$$$ 最大化。
如果有多个解,则可以输出任意一个。
示例
输入 #1
7 5 1 3 2 2 4 5 1 2 3 4 5 4 2 1 2 1 3 2 3 3 2 2 2 1 1 9 9 8 5 2 1 1 2 3 3
输出 #1
2 4 1 5 1 4 2 3 1 2 1 1 3 9
注意
在第一个测试用例中,$$$a=[1,3,2,2,4]$$$。
- 当 $$$l=1$$$ 且 $$$r=3$$$ 时,$$$c(l,r)=3$$$ ($$$[1,3,2]$$$ 中有 $$$3$$$ 不同元素)。
- 当 $$$l=2$$$ 且 $$$r=4$$$ 时,$$$c(l,r)=2$$$ ($$$[3,2,2]$$$ 中有 $$$2$$$ 不同元素)。
可以证明,选择 $$$l=2$$$ 和 $$$r=4$$$ 可以最大化 $$$r-l-c(l,r)$$$ 在 $$$0$$$ 处的值。
对于第二个测试用例,$$$a=[1,2,3,4,5]$$$。
- 当 $$$l=1$$$ 且 $$$r=5$$$ 时,$$$c(l,r)=5$$$ ($$$[1,2,3,4,5]$$$ 中有 $$$5$$$ 不同元素)。
- 当$$$l=3$$$且$$$r=3$$$时,$$$c(l,r)=1$$$($$$[3]$$$中有$$$1$$$不同元素)。
可以证明,选择 $$$l=1$$$ 和 $$$r=5$$$ 可以最大化 $$$r-l-c(l,r)$$$ 在 $$$-1$$$ 处的值。选择 $$$l=3$$$ 和 $$$r=3$$$ 也是可以接受的。