Your task is very simple, and even without big legend: you just need to find the maximum on a segment. \InputFile Initially the number of elements $n~(1 \le n \le 10^5)$ in array is given. The next line contains $n$ numbers --- the initial array $a_1, a_2, ..., a_n~(-10^9 \le a_i \le 10^9)$. Next line contains the number of queries $q~(1 \le q \le 5 \cdot 10^5)$. Each of the next $q$ lines contain two positive integers $l$ and $r~(1 \le l, r \le n)$ --- the segment, where you must find the maximum. \OutputFile For each query print the maximum on a segment.