Максимум

Проста

Обмеження на час виконання 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%