Реализуйте структуру данных для эффективного вычисления номера максимального из нескольких подряд идущих элементов массива.
Входные данные
В первой строке вводится одно натуральное число
N (
\(1 <= N <= 100000\)) — количество чисел в массиве.
Во второй строке вводятся
N чисел от 1 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число
K (
\(1 <= K <= 30000\)) — количество запросов на вычисление максимума.
В следующих
K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).
Выходные данные
Для каждого запроса выведите индекс максимального элемента на указанном отрезке массива. Если максимальных элементов несколько, выведите любой их них.
Числа выводите в одну строку через пробел.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 2 2 1 5
2
2 3
2 5
|
2 5
|