Dora and Search
Contest: Codeforces Round 852 (Div. 2)
Difficulty rating: 1200
Tags: constructive algorithms, data structures, two pointers

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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(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.

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

Example output:
-1
1 4
2 6
-1

Editorial:
Suppose we want to check whether the entire array satisfies the claim. If this is the case, then we can output the entire array as an answer. Otherwise, one of the two extreme elements does not meet our requirements. From this we can conclude that all segments containing an element that does not meet our requirements will also be incorrect, because this extreme element will remain the minimum/maximum.
The algorithm follows from the fact above: let's look at the sub-section $$$[l; r]$$$, which is initially equal to $$$[1; n]$$$. If $$$a_l = \min(a_{l}, a_{l+1}, \ldots, a_{r})$$$ or $$$a_l = \max(a_l, a_{l +1}, \ldots, a_r)$$$, then we proceed to the segment $$$[l+1; r]$$$. A similar reasoning is also needed for $$$a_r$$$. Thus, either after some iterations we will get the required sub-section, or we will get $$$l == r$$$ and the answer will be $$$-1$$$.
Final asymptotics: $$$\mathcal{O}(n\log n)$$$ or $$$\mathcal(O)(n)$$$ depending on the implementation.