Dora and Search

题意翻译

### 题目描述 给定一个长度为 $n$ 的排列 $a$ ，问是否存在正整数 $l,r$ 使得 $a_l,a_r$ 均不为 $a_{l...r}$ 中的最大值或最小值。 ### 输入输出格式 第一行一个正整数 $t$ ，表示数据组数。接下来对于每组数据输入包括两行，第一行一个正整数 $n$ ，第二行 $n$ 个正整数代表排列 $a$ 。\ 对于每组数据，若存在符合要求的 $l,r$ ，输出任意一组。若不存在则输出 $-1$ 。 ### 数据范围 $1\leqslant t \leqslant 10\ 000\ ,\ 1\leqslant \Sigma n \leqslant 200\ 000\ ,\ $ $a$ 是一个排列。

题目描述

As you know, the girl Dora is always looking for something. This time she was given a permutation, and she wants to find such a subsegment of it that none of the elements at its ends is either the minimum or the maximum of the entire subsegment. More formally, you are asked to find the numbers $ l $ and $ r $ $ (1 \leq l \leq r \leq n) $ such that $ a_l \neq \min(a_l, a_{l + 1}, \ldots, a_r) $ , $ a_l \neq \max(a_l, a_{l + 1}, \ldots, a_r) $ and $ a_r \neq \min(a_l, a_{l + 1}, \ldots, a_r) $ , $ a_r \neq \max(a_l, a_{l + 1}, \ldots, a_r) $ . A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in any order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ occurs twice in the array) and $ [1,3,4] $ is also not a permutation ( $ n=3 $ , but $ 4 $ is present in the array). Help Dora find such a subsegment, or tell her that such a subsegment does not exist.

输入输出格式

输入格式

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. Description of the test cases follows. For each test case, the first line contains one integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the length of permutation. The second line contains $ n $ distinct integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ) — the elements of permutation. It is guarented that the sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output $ -1 $ if the desired subsegment does not exist. Otherwise, output two indexes $ l, r $ such that $ [a_{l}, a_{l + 1}, \ldots, a_{r}] $ satisfies all conditions. If there are several solutions, then output any of them.

输入输出样例

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

说明

In the first and fourth test cases, it can be shown that there are no desired subsegments. In the second test case, the subsegment $ [1, 4] $ satisfies all the conditions, because $ \max(a_1, a_2, a_3, a_4) = 4, \min(a_1, a_2, a_3, a_4) = 1 $ , as we see, all the conditions are met. In the third test case, the subsegment $ [2, 6] $ also satisfies all the conditions described.

**题意翻译**

### 题目描述
给定一个长度为 $n$ 的排列 $a$ ，问是否存在正整数 $l,r$ 使得 $a_l,a_r$ 均不为 $a_{l...r}$ 中的最大值或最小值。

### 输入输出格式
第一行一个正整数 $t$ ，表示数据组数。接下来对于每组数据输入包括两行，第一行一个正整数 $n$ ，第二行 $n$ 个正整数代表排列 $a$ 。对于每组数据，若存在符合要求的 $l,r$ ，输出任意一组。若不存在则输出 $-1$ 。

### 数据范围
$1\leqslant t \leqslant 10\ 000\ ,\ 1\leqslant \Sigma n \leqslant 200\ 000\ ,\ $ $a$ 是一个排列。

**题目描述**

朵拉总在寻找些什么。这次她得到了一个排列，她想要找到一个子段，使得这个子段两端的元素都不是整个子段的最大值或最小值。形式化地说，需要找到数 $ 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 $ ）。

帮助朵拉找到这样的子段，或者告诉她这样的子段不存在。

**输入输出格式**

**输入格式**
每个测试由多个测试案例组成。第一行包含一个整数 $ 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] $ 也满足所有描述的条件。**题意翻译** ### 题目描述 给定一个长度为 $n$ 的排列 $a$ ，问是否存在正整数 $l,r$ 使得 $a_l,a_r$ 均不为 $a_{l...r}$ 中的最大值或最小值。 ### 输入输出格式 第一行一个正整数 $t$ ，表示数据组数。接下来对于每组数据输入包括两行，第一行一个正整数 $n$ ，第二行 $n$ 个正整数代表排列 $a$ 。对于每组数据，若存在符合要求的 $l,r$ ，输出任意一组。若不存在则输出 $-1$ 。 ### 数据范围 $1\leqslant t \leqslant 10\ 000\ ,\ 1\leqslant \Sigma n \leqslant 200\ 000\ ,\ $ $a$ 是一个排列。 **题目描述** 朵拉总在寻找些什么。这次她得到了一个排列，她想要找到一个子段，使得这个子段两端的元素都不是整个子段的最大值或最小值。形式化地说，需要找到数 $ 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 $ ）。 帮助朵拉找到这样的子段，或者告诉她这样的子段不存在。 **输入输出格式** **输入格式** 每个测试由多个测试案例组成。第一行包含一个整数 $ 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] $ 也满足所有描述的条件。