Реализуйте структуру данных, которая на данном массиве из $N$ целых чисел позволяет узнать максимальное значение на этом массиве и индекс элемента, на котором достигается это максимальное значение.
В первой строке вводится натуральное число $N$ ($1 \leq N \leq 10^5$) -- количество элементов в массиве. В следующей строке содержатся $N$ целых чисел, не превосходящих по модулю $10^9$ -- элементы массиваб гарантируется, что в массиве нет одинаковых элементов. Далее идет число $K$ ($0 \leq K \leq 10^5$) -- количество запросов к структуре данных. Каждая из следующих $K$ строк содержит два целых числа $l$ и $r$ ($1 \leq l \leq r \leq N$) -- левую и правую границы отрезка в массиве для данного запроса.
Для каждого из запросов выведите два числа: наибольшее значение среди элементов массива на отрезке от $l$ до $r$ и индекс одного из элементов массива, принадлежащий отрезку от $l$ до $r$, на котором достигается этот максимум.