Реализуйте структуру данных, которая на данном массиве из N целых чисел позволяет узнать максимальное значение на этом массиве и индекс элемента, на котором достигается это максимальное значение.
Входные данные
В первой строке вводится натуральное число N (1 ≤ N ≤ 10
5) – количество элементов в массиве. В следующей строке содержатся N целых чисел, не превосходящих по модулю 10
9 – элементы массива. Далее идет число K (0 ≤ K ≤ 10
5) – количество запросов к структуре данных. Каждая из следующих K строк содержит два целых числа l и r (1 ≤ l ≤ r ≤ N) – левую и правую границы отрезка в массиве для данного запроса.
Выходные данные
Для каждого из запросов выведите два числа: наибольшее значение среди элементов массива на отрезке от l до r и индекс одного из элементов массива, принадлежащий отрезку от l до r, на котором достигается этот максимум.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
7 3 1 6 4
3
1 5
2 4
3 3
|
7 1
6 4
1 3
|
|
2
|
1
0
1
1 1
|
0 1
|
|
3
|
2
0 1
3
1 1
1 2
2 2
|
0 1
1 2
1 2
|