← 返回题目列表

Codeforces · 1927/D

D. 找到不同的!

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

给您一个包含 $$$n$$$ 整数的数组 $$$a$$$ 和 $$$q$$$ 查询。

每个查询由两个整数 $$$l$$$ 和 $$$r$$$ 表示 ($$$1 \le l \le r \le n$$$)。您的任务是为每个查询找到两个索引 $$$i$$$ 和 $$$j$$$ (或确定它们不存在),使得:

- $$$l \le i \le r$$$;
- $$$l \le j \le r$$$;
- $$$a_i \ne a_j$$$。

换句话说,对于每个查询,您需要在 $$$a_l, a_{l+1}, \dots, a_r$$$ 中找到一对不同的元素,否则报告这样的一对不存在。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 数组 $$$a$$$ 的元素。

每个测试用例的第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行每行包含两个整数,$$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le n$$$) - 查询的边界。

保证所有测试用例中 $$$n$$$ 的值之和不超过 $$$2 \cdot 10^5$$$。同样,保证所有测试用例中 $$$q$$$ 的值之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个查询,输出两个以空格分隔的整数:$$$i$$$ 和 $$$j$$$ ($$$l \le i, j \le r$$$),其中 $$$a_i \ne a_j$$$。如果这样的对不存在,则输出 $$$i=-1$$$ 和 $$$j=-1$$$。

您可以用空行分隔测试用例的输出。这不是强制性要求。

示例

输入 #1

5
5
1 1 2 1 1
3
1 5
1 2
1 3
6
30 20 20 10 10 20
5
1 2
2 3
2 4
2 6
3 5
4
5 2 3 4
4
1 2
1 4
2 3
2 4
5
1 4 3 2 4
5
1 5
2 4
3 4
3 5
4 5
5
2 3 1 4 2
7
1 2
1 4
1 5
2 4
2 5
3 5
4 5

输出 #1

2 3
-1 -1
1 3

2 1
-1 -1
4 2
4 6
5 3

1 2
1 2
2 3
3 2

1 3
2 4
3 4
5 3
5 4

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