Максимум

Вхідні дані

Перший рядок містить ціле число $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) — кількість елементів у масиві.

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n} (- 1 0^{9} \leq a_{i} \leq 1 0^{9})$ a_1, a_2, \ldots, a_n~(-10^9 \le a_i \le 10^9) — елементи масиву.

Третій рядок містить ціле число $q (1 \leq q \leq 5 \cdot 1 0^{5})$ q~(1 \le q \le 5 \cdot 10^5) — кількість запитів.

Кожен з наступних $q$ рядків містить два додатних числа $l$ та $r (1 \leq l, r \leq n)$ r~(1 \le l, r \le n), що представляють кінці діапазону. Для кожного запиту потрібно знайти максимальне значення у підмасиві від позиції $l$ до позиції $r$ включно.

Вихідні дані

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

Приклади

Приклад 1

Loading