给定长度为N的序列，M个询问，每次询问两个数字A,B，要求求出属于A到B这段区间内的最大数。
一个整数N表示数字的个数,接下来一行为N个数。第三行读入一个M，表示你看完那串数后需要被提问的次数，接下来M行，每行都有两个整数A,B。
输出共M行，每行输出一个数。
6
34 1 8 123 3 2
4
1 2
1 5
3 4
2 3 34
123
123
8 对40%：$N \le 6000, M \le 500 $
对100%： $ N \le 200000, M \le 10000$,
所有数均在int范围内