# 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≤n≤10_{5})$ in array is given. The next line contains $n$ numbers — the initial array $a_{1},a_{2},...,a_{n}(−10_{9}≤a_{i}≤10_{9})$. Next line contains the number of queries $q(1≤q≤5⋅10_{5})$. Each of the next $q$ lines contain two positive integers $l$ and $r(1≤l,r≤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%