如你所知,女孩朵拉总是在寻找一些东西。这次她得到了一个排列,她想找到它的一个子段,使得其末尾的元素都不是整个子段的最小值或最大值。更正式地说,要求您查找数字 $$$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]$$$ 也满足所描述的所有条件。