Doremy's Paint

题意翻译

Doremy 有 $n$ 桶油漆，用一个长度为 $n$ 的序列 $a$ 表示。第 $i$ 个桶中的颜料编号为 $a_i$。定义 $c(l,r)$ 为从 $a_l$ 到 $a_r$ 的子串中颜料种类的数量（及相同的颜料只算一次）。请找出一对 $l$ 和 $r$ 使得 $l \leq r$ 并且 $r-l-c(l,r)$ 的值最大。

题目描述

Doremy has $ n $ buckets of paint which is represented by an array $ a $ of length $ n $ . Bucket $ i $ contains paint with color $ a_i $ . Let $ c(l,r) $ be the number of distinct elements in the subarray $ [a_l,a_{l+1},\ldots,a_r] $ . Choose $ 2 $ integers $ l $ and $ r $ such that $ l \leq r $ and $ r-l-c(l,r) $ is maximized.

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1\le t\le 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the array $ a $ . The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le n $ ). It is guaranteed that the sum of $ n $ does not exceed $ 10^5 $ .

输出格式

For each test case, output $ l $ and $ r $ such that $ l \leq r $ and $ r-l-c(l,r) $ is maximized. If there are multiple solutions, you may output any.

输入输出样例

输入样例 #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

说明

In the first test case, $ a=[1,3,2,2,4] $ . - When $ l=1 $ and $ r=3 $ , $ c(l,r)=3 $ (there are $ 3 $ distinct elements in $ [1,3,2] $ ). - When $ l=2 $ and $ r=4 $ , $ c(l,r)=2 $ (there are $ 2 $ distinct elements in $ [3,2,2] $ ). It can be shown that choosing $ l=2 $ and $ r=4 $ maximizes the value of $ r-l-c(l,r) $ at $ 0 $ . For the second test case, $ a=[1,2,3,4,5] $ . - When $ l=1 $ and $ r=5 $ , $ c(l,r)=5 $ (there are $ 5 $ distinct elements in $ [1,2,3,4,5] $ ). - When $ l=3 $ and $ r=3 $ , $ c(l,r)=1 $ (there is $ 1 $ distinct element in $ [3] $ ). It can be shown that choosing $ l=1 $ and $ r=5 $ maximizes the value of $ r-l-c(l,r) $ at $ -1 $ . Choosing $ l=3 $ and $ r=3 $ is also acceptable.

**多雷米的油漆**

**题意翻译：**
多雷米有 $ n $ 桶油漆，用长度为 $ n $ 的序列 $ a $ 表示。第 $ i $ 个桶中的颜料编号为 $ a_i $。定义 $ c(l,r) $ 为从 $ a_l $ 到 $ a_r $ 的子串中颜料种类的数量（即相同的颜料只算一次）。请找出一对 $ l $ 和 $ r $ 使得 $ l \leq r $ 并且 $ r-l-c(l,r) $ 的值最大。

**题目描述：**
多雷米有 $ n $ 桶油漆，用长度为 $ n $ 的数组 $ a $ 表示。桶 $ i $ 包含颜色为 $ a_i $ 的油漆。

定义 $ c(l,r) $ 为在子数组 $ [a_l,a_{l+1},\ldots,a_r] $ 中不同元素的数量。选择两个整数 $ 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 $ 也是可接受的。**多雷米的油漆** **题意翻译：** 多雷米有 $ n $ 桶油漆，用长度为 $ n $ 的序列 $ a $ 表示。第 $ i $ 个桶中的颜料编号为 $ a_i $。定义 $ c(l,r) $ 为从 $ a_l $ 到 $ a_r $ 的子串中颜料种类的数量（即相同的颜料只算一次）。请找出一对 $ l $ 和 $ r $ 使得 $ l \leq r $ 并且 $ r-l-c(l,r) $ 的值最大。 **题目描述：** 多雷米有 $ n $ 桶油漆，用长度为 $ n $ 的数组 $ a $ 表示。桶 $ i $ 包含颜色为 $ a_i $ 的油漆。 定义 $ c(l,r) $ 为在子数组 $ [a_l,a_{l+1},\ldots,a_r] $ 中不同元素的数量。选择两个整数 $ 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 $ 也是可接受的。