Consider an array A of n integers.
Given a search range [l, r],
find the maximum value inside the search range in A.
Note that 1<= l <= r <= n , and size of the elements in A are constrained in INT32.
The first line contains an integer n. (1<=n<1000)
The second line contains n integers as the elements of A.
The third line contains an integer t.
Each of the following t lines contains two integers l_t and r_t denoting the search range [l_t, r_t] in A.
The output contains t lines.
Each line shows the maximum integer inside the corresponding search range in A.
There is a '\n' at the end of each line.