1793C. Dora and Search

constructive algorithms, data structures, two pointers, 1200,

https://codeforces.com/problemset/problem/1793/C

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 𝑙 and 𝑟 (1≤𝑙≤𝑟≤𝑛) such that $𝑎𝑙\ne min({𝑎}_{𝑙},{𝑎}_{𝑙+1},\dots ,{𝑎}_{𝑟})$, $𝑎𝑙\ne max({𝑎}_{𝑙},{𝑎}_{𝑙+1},\dots ,{𝑎}_{𝑟})$ and $𝑎𝑟\ne min({𝑎}_{𝑙},{𝑎}_{𝑙+1},\dots ,{𝑎}_{𝑟})$, $𝑎𝑟\ne max({𝑎}_{𝑙},{𝑎}_{𝑙+1},\dots ,{𝑎}_{𝑟})$.

A permutation of length 𝑛 is an array consisting of 𝑛 distinct integers from 11 to 𝑛 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][1,3,4] is also not a permutation (𝑛=3, but 4 is present in the array).

Help Dora find such a subsegment, or tell her that such a subsegment does not exist.

Input

Each test consists of multiple test cases. The first line contains a single integer $𝑡(1\le 𝑡\le {10}^4)$ — the number of test cases. Description of the test cases follows.

For each test case, the first line contains one integer $𝑛(1\le 𝑛\le 2\cdot {10}^5)$ — the length of permutation.

The second line contains 𝑛 distinct integers ${𝑎}_1,{𝑎}_2,\dots ,{𝑎}_{𝑛}(1\le {𝑎}_{𝑖}\le 𝑛)$ — the elements of permutation.

It is guarented that the sum of 𝑛 over all test cases doesn't exceed 2⋅1052⋅105.

Output

For each test case, output −1−1 if the desired subsegment does not exist.

Otherwise, output two indexes 𝑙,𝑟 such that $[{𝑎}_{𝑙},{𝑎}_{𝑙+1},\dots ,{𝑎}_{𝑟}]$ satisfies all conditions.

If there are several solutions, then output any of them.

Example

input

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

output

-1
1 4
2 6
-1

Note

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({𝑎}_1,{𝑎}_2,{𝑎}_3,{𝑎}_4)=4,min({𝑎}_1,{𝑎}_2,{𝑎}_3,{𝑎}_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.

参考：https://blog.csdn.net/lmb_f/article/details/129077484

题目大意：给你个n的排列，找出是否存在$a_l,a_{l+1},...,a_r$的子序列满足端点不是区间最大和最小。

思路

因为题目只要有1个满足就好，所以我们从（1，n）开始缩小（因为此时最大值就是n，最小值是1）

然后根据要求移动l和r就行

如果a[l]是最大值，l++,max--; 如果a[l]是最小值,l++,min++; 如果a[r]是最大值，r--,max--; 如果a[r]是最小值,r--,min++;

num = []
t = int(input())

for _ in range(t):
    n = int(input())
    num = list(map(int, input().split()))
    l = 1
    r = n
    vmin = 1
    vmax = n

    while l < r:
        if num[l-1] == vmin:
          l += 1
          vmin += 1
        elif num[l-1] == vmax:
          l += 1
          vmax -= 1
        elif num[r-1] == vmin:
          r -= 1
          vmin += 1
        elif num[r-1] == vmax:
          r -= 1
          vmax -= 1
        else:
          break

    if l < r:
        print(l, r)
    else:
        print(-1)