Ваша задача дуже проста і навіть без великої історії: просто потрібно знайти максимум на відрізку. \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 Для кожного запиту виведіть максимум на заданому відрізку.