Problem D: PIPI打怪Ⅲ

Problem D: PIPI打怪Ⅲ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 189  Solved: 54
[Submit] [Status] [Web Board] [Creator:]

Description

在修炼场地图中,从左到右一共有n只怪物,战胜第i只怪物将会获得ai的经验值。规定[l,r]区间中,怪物经验值的最小值为该区间的价值。
现在PIPI接受了q个任务,每个任务会要求PIPI选择一个长度为len的区间,将里面的怪物全部杀死。因为怪物刷新时间很快,所以PIPI每次提交完一个任务,被杀死的怪物将全部复活。
现在PIPI想知道,对于每个任务,他能选择的区间中,价值最大的是多少?

Input

第一行一个正整数n,n<=10^6。
第二行n个正整数ai,ai<=10^9。
第三行一个正整数q,q<=10^6。
接下来q行,每行一个正整数len,len<=n。

Output

对于每个任务,输出最大区间价值。

Sample Input

3
1 2 3
3
3
2
1

Sample Output

1
2
3

HINT

样例解释:
对于长度为3的区间,总共有[1,3]一个,其区间价值为1,因此答案为1。 
对于长度为2的区间,总共有[1,2],[2,3]两个,其区间价值为1,2,里面的最大值为2,因此答案为2。 
对于长度为1的区间,总共有[1,1],[2,2],[3,3]三个,其区间价值为1,2,3,里面的最大值为3,因此答案为3。