Maximum

Easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

Your task is very simple, and even without big legend: you just need to find the maximum on a segment.

Input

Initially the number of elements $n (1 \leq n \leq 1 0^{5})$ in array is given. The next line contains $n$ numbers — the initial array $a_{1}, a_{2}, ..., a_{n} (- 1 0^{9} \leq a_{i} \leq 1 0^{9})$ . Next line contains the number of queries $q (1 \leq q \leq 5 \cdot 1 0^{5})$ . Each of the next $q$ lines contain two positive integers $l$ and $r (1 \leq l, r \leq n)$ — the segment, where you must find the maximum.

Output

For each query print the maximum on a segment.

Examples

Input #1

Answer #1

Submissions 6K

Acceptance rate 19%