Ваша задача очень простая и даже без большой легенды: просто нужно найти максимум на отрезке. \InputFile Сначала подаётся количество чисел $n~(1 \le n \le 10^5)$ в массиве. В следующей строке заданы $n$ чисел – исходный массив $a_1, a_2, ..., a_n~(-10^9 \le a_i \le 10^9)$. Следующая строка содержит количество запросов $q~(1 \le q \le 5 \cdot 10^5)$. Каждая из следующих $q$ строк содержит по два натуральных числа $l$ и $r~(1 \le l, r \le n)$ --- отрезок, на котором следует найти максимум. \OutputFile Для каждого запроса выведите максимум на заданном отрезке.