5443：The Water Problem

In Land waterless, water is a very limited resource. People always fight for the biggest source of water. Given a sequence of water sources with $a_1, a_2, a_3, . . . , a_n$ representing the size of the water source. Given a set of queries each containing $2$ integers $l$ and $r$, please find out the biggest water source between $a_l$ and $a_r$.

First you are given an integer $T (T \leq 10)$ indicating the number of test cases. For each test case, there is a number $n (0 \leq n \leq 1000)$ on a line representing the number of water sources. $n$ integers follow, respectively $a_1, a_2, a_3, . . . , a_n$, and each integer is in $\{1, . . . , 10^6\}$. On the next line, there is a number $q (0 \leq q \leq 1000)$ representing the number of queries. After that, there will be $q$ lines with two integers $l$ and $r (1 \leq l \leq r \leq n)$ indicating the range of which you should find out the biggest water source.

For each query, output an integer representing the size of the biggest water source.