将任意数组 $$$b$$$ 的分数定义为 $$$b$$$ 的长度减去 $$$b$$$ 中不同元素的数量。例如:
- $$$[1, 2, 2, 4]$$$ 的得分为 $$$1$$$,因为它的长度为 $$$4$$$,并且只有 $$$3$$$ 个不同元素($$$1$$$、$$$2$$$、$$$4$$$)。
- $$$[1, 1, 1]$$$ 的得分为 $$$2$$$,因为它的长度为 $$$3$$$ 并且只有 $$$1$$$ 不同元素 ($$$1$$$)。
- 空数组的得分为 $$$0$$$。
你有一个数组$$$a$$$。你需要删除一些 非空 来自 $$$a$$$ 的连续子数组 最多 一次。
更正式地说,您可以执行以下操作 最多 一次:
- 选择两个整数 $$$l$$$, $$$r$$$ 其中 $$$1 \le l \le r \le n$$$,并且
- 从 $$$a$$$ 中删除连续子数组 $$$[a_l,\ldots,a_r]$$$ (即将 $$$a$$$ 替换为 $$$[a_1,\ldots,a_{l - 1},a_{r + 1},\ldots,a_n]$$$)。
输出一个运算,使得 $$$a$$$ 的分数为 最大;如果有多个答案,则输出一个 最小化 操作后$$$a$$$的最终长度。如果仍有多个答案,则可以输出其中任何一个。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果您不想移动,请输出 $$$0$$$。
否则,输出两个整数$$$l$$$和$$$r$$$ ($$$1 \le l \le r \le n$$$),代表移除子数组的左右边界。
应选择删除的子数组,以使分数最大化,并且在所有此类答案中选择其中任何一个,使数组的最终长度最小化。
示例
输入复制
31151 1 1 1 142 1 3 2
输出复制
1 1 0 2 3
注意
在第一个测试用例中,我们有两个选择:
- 不执行任何操作:$$$[1]$$$ 的分数为 $$$1-1=0$$$。
- 删除 $$$l=1$$$, $$$r=1$$$ 的子数组:我们删除唯一的元素,得到一个得分为 $$$0$$$ 的空数组。
在第二个测试用例中,没有选择子数组,因此 $$$a$$$ 仍然是 $$$[1, 1, 1, 1, 1]$$$。它的长度为 $$$5$$$ 和 $$$1$$$ 不同元素,因此它的分数为 $$$5 - 1 = 4$$$。可以证明这是一个使分数最大化的最短数组。
在第三个测试用例中,选择的子数组是 $$$[2, \color{red}1, \color{red}3, 2]$$$,之后 $$$a$$$ 变为 $$$[2, 2]$$$。它的长度为 $$$2$$$ 和 $$$1$$$ 不同元素,因此它的分数为 $$$2 - 1 = 1$$$。可以证明这是一个使分数最大化的最短数组。