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