Given array of integers a1,...,an. For given indexes l and r find
The first line contains the amount of numbers n (1≤n≤106). The second line contains the numbers ai (1≤ai≤1000). The third line contains the number of queries m (1≤m≤106). Each of the next line contains the query li and ri (1≤li≤ri≤n).
Print in separate m lines the numbers S[li...ri].