← 返回题目列表

Codeforces · 1793/C

C. 朵拉和搜索

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

如你所知,女孩朵拉总是在寻找一些东西。这次她得到了一个排列,她想找到它的一个子段,使得其末尾的元素都不是整个子段的最小值或最大值。更正式地说,要求您查找数字 $$$l$$$ 和 $$$r$$$ $$$(1 \leq l \leq r \leq n)$$$ 使得 $$$a_l \neq \min(a_l, a_{l + 1}, \ldots, a_r)$$$, $$$a_l \neq \max(a_l, a_{l + 1}, \ldots, a_r)$$$ 和 $$$a_r \neq \min(a_l, a_{l + 1}, \ldots, a_r)$$$, $$$a_r \neq \max(a_l, a_{l + 1}, \ldots, a_r)$$$。

长度 $$$n$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 可以任意顺序。例如,$$$[2,3,1,5,4]$$$ 是排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),并且 $$$[1,3,4]$$$ 也不是排列($$$n=3$$$,但 $$$4$$$ 出现在数组中)。

帮助Dora找到这样的子段,或者告诉她这样的子段不存在。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 排列的长度。

第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — 排列的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果所需的子段不存在,则输出 $$$-1$$$。

否则,输出两个索引 $$$l, r$$$ 使得 $$$[a_{l}, a_{l + 1}, \ldots, a_{r}]$$$ 满足所有条件。

如果有多个解,则输出其中任意一个。

示例

输入 #1

4
3
1 2 3
4
2 1 4 3
7
1 3 2 4 6 5 7
6
2 3 6 5 4 1

输出 #1

-1
1 4
2 6
-1

注意

在第一个和第四个测试用例中,可以表明不存在所需的子段。

在第二个测试用例中,子段 $$$[1, 4]$$$ 满足所有条件,因为 $$$\max(a_1, a_2, a_3, a_4) = 4, \min(a_1, a_2, a_3, a_4) = 1$$$,正如我们所见,所有条件都满足。

在第三个测试用例中,子段 $$$[2, 6]$$$ 也满足所描述的所有条件。