问题描述

fzk特别擅长拼图游戏,作为科大ACM/ICPC代表队STUDENT的主力成员,他每逢大赛前必然要买一个新的
拼图来玩拼图游戏,据说可以攒人品哦!所以迄今为止,fzk已经玩过了好多不同的拼图游戏,我们可
以记作 Game1,Game2,Game3,……,GameN。每次他都会记录下来完成拼图的时间,分别是 
Time1,Time2,Time3,……,TimeN(单位:分钟)。gzsun十分嫉妒fzk的拼图能力,所以往往故意刁难fzk
,问他:“老范,你好年轻啊,hiahia~~。那么从Gamei到Gamej,你完成一个拼图用的最少时间是多少
啊?”这下可难坏了fzk,你能不能帮助fzk回答gzsun呢?

问题输入

首先一个整数t表示测试数据组数(1=<t<=10)。对每组数据,第一行是一个整数N(0<N<=30000),表
示总共玩的游戏数。接下来的的一行中是N个整数,对应于Time1…TimeN(都是不超过1000000000的正整
数)。然后是一个整数M(0<M<=30000),表示gzsun的询问次数。接下来的M行中每行有两个正整数i,j
,1<=i<j<=N。

问题输出

对每组测试数据中的每次询问(i,j),输出一个正整数t,使得t = min{Timek, i<=k<=j}。

样例输入

1
4
5 3 7 2
3
1 4
2 3
4 4

样例输出

2
3
2