Максимум

Простая

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

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

Входные данные

Сначала подаётся количество чисел $n (1 \leq n \leq 1 0^{5})$ в массиве. В следующей строке заданы $n$ чисел – исходный массив $a_{1}, a_{2}, ..., a_{n} (- 1 0^{9} \leq a_{i} \leq 1 0^{9})$ . Следующая строка содержит количество запросов $q (1 \leq q \leq 5 \cdot 1 0^{5})$ . Каждая из следующих $q$ строк содержит по два натуральных числа $l$ и $r (1 \leq l, r \leq n)$ — отрезок, на котором следует найти максимум.

Выходные данные

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

Примеры

Ввод #1

Ответ #1

Отправки 6K

Коэффициент принятия 19 %