← 返回题目列表

Codeforces · 1764/A

A. 多米的油漆

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

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$$$ 也是可以接受的。