Maximum — Eolymp

Input

The first line contains an integer $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) — the number of elements in the array.

The second line contains $n$ integers $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) — the elements of the array.

The third line contains an integer $q (1 \leq q \leq 5 \cdot 1 0^{5})$ q~(1 \le q \le 5 \cdot 10^5) — the number of queries.

Each of the next $q$ lines contains two positive integers $l$ and $r (1 \leq l, r \leq n)$ r~(1 \le l, r \le n), representing the endpoints of a range. For each query, you must find the maximum value in the subarray from position $l$ to position $r$ , inclusive.

Output

For each query, print the maximum value in the corresponding range.

Examples

Example 1

Loading