Реализуйте структуру данных для эффективного вычисления максимумов подряд идущих элементов массива.
Входные данные
В первой строке вводится одно натуральное число
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 |