← 返回题目列表

Codeforces · 2064/B

B. 不鼓励多样化

中文机器翻译题面 查看原题

将任意数组 $$$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$$$),代表移除子数组的左右边界。

应选择删除的子数组,以使分数最大化,并且在所有此类答案中选择其中任何一个,使数组的最终长度最小化。

示例

输入
复制

3
1
1
5
1 1 1 1 1
4
2 1 3 2

输出
复制

1 1
0
2 3

注意

在第一个测试用例中,我们有两个选择:

  • 不执行任何操作:$$$[1]$$$ 的分数为 $$$1-1=0$$$。
  • 删除 $$$l=1$$$, $$$r=1$$$ 的子数组:我们删除唯一的元素,得到一个得分为 $$$0$$$ 的空数组。
因此,可能的最高分数是 $$$0$$$。然而,由于我们需要另外最小化数组的最终长度,所以我们 必须 输出第二个选项$$$l=r=1$$$。请注意,第一个不执行任何操作的选项是 不正确,因为它的最终长度更长。

在第二个测试用例中,没有选择子数组,因此 $$$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$$$。可以证明这是一个使分数最大化的最短数组。