B. Максимум и его место

Дан массив, все элементы которого попарно различны. Массив не меняется. Для каждого запроса выведите максимальное значение на отрезке и индекс элемента, на котором этот максимум достигается.

В первой строке $n$ ($1 \le n \le 10^5$). Во второй — $n$ попарно различных чисел $a_i$ ($|a_i| \le 10^9$). В третьей — $k$ ($1 \le k \le 2 \cdot 10^5$). В каждой из следующих $k$ строк — $l$ и $r$ ($1 \le l \le r \le n$).

Для каждого запроса выведите на отдельной строке два числа: максимум на отрезке и индекс, на котором он достигается.