Вам дан массив \(a\) из \(n\) целых чисел, а также \(q\) запросов.
Каждый запрос представлен двумя числами \(l\) и \(r\) (\(1 \le l \le r \le n\)). Ваша задача для каждого запроса найти такие два индекса \(i\) и \(j\) (или сообщить, что их не существует), что:
- \(l \le i \le r\);
- \(l \le j \le r\);
- \(a_i \ne a_j\).
Иными словами, вам нужно для каждого запроса найти пару различных элементов среди \(a_l, a_{l+1}, \dots, a_r\) или сообщить, что такой пары не существует.
Выходные данные
Для каждого запроса выведите два числа: искомые \(i\) и \(j\) (\(l \le i, j \le r\)), для которых \(a_i \ne a_j\). Если такой пары не существует, выведите \(i=-1\) и \(j=-1\).
Вы можете разделять выводы для наборов входных данных пустыми строками. Это не является обязательным требованием.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
1 1 2 1 1
3
1 5
1 2
1 3
6
30 20 20 10 10 20
5
1 2
2 3
2 4
2 6
3 5
4
5 2 3 4
4
1 2
1 4
2 3
2 4
5
1 4 3 2 4
5
1 5
2 4
3 4
3 5
4 5
5
2 3 1 4 2
7
1 2
1 4
1 5
2 4
2 5
3 5
4 5
|
2 3
-1 -1
1 3
2 1
-1 -1
4 2
4 6
5 3
1 2
1 2
2 3
3 2
1 3
2 4
3 4
5 3
5 4
1 2
4 2
1 3
2 3
3 2
5 4
5 4
|