CF1927D.Find the Different Ones!

You are given an array $a$ of $n$ integers, and $q$ queries.

Each query is represented by two integers $l$ and $r$ ( $1 \le l \le r \le n$ ). Your task is to find, for each query, two indices $i$ and $j$ (or determine that they do not exist) such that:

• $l \le i \le r$ ;
• $l \le j \le r$ ;
• $a_i \ne a_j$ .

In other words, for each query, you need to find a pair of different elements among $a_l, a_{l+1}, \dots, a_r$ , or report that such a pair does not exist.

The first line of the input contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ( $2 \le n \le 2 \cdot 10^5$ ) — the length of the array $a$ .

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^6$ ) — the elements of the array $a$ .

The third line of each test case contains a single integer $q$ ( $1 \le q \le 2 \cdot 10^5$ ) — the number of queries.

The next $q$ lines contain two integers each, $l$ and $r$ ( $1 \le l < r \le n$ ) — the boundaries of the query.

It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2 \cdot 10^5$ . Similarly, it is guaranteed that the sum of the values of $q$ across all test cases does not exceed $2 \cdot 10^5$ .

For each query, output two integers separated by space: $i$ and $j$ ( $l \le i, j \le r$ ), for which $a_i \ne a_j$ . If such a pair does not exist, output $i=-1$ and $j=-1$ .

You may separate the outputs for the test cases with empty lines. This is not a mandatory requirement.