给您一个包含 $$$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