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.