Your task is very simple, and even without big legend: you just need to find the maximum on a segment.
Initially the number of elements n (1≤n≤105) in array is given. The next line contains n numbers — the initial array a1,a2,...,an (−109≤ai≤109). Next line contains the number of queries q (1≤q≤5⋅105). 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.
For each query print the maximum on a segment.