给你N个正整数，每个数在均小于等于1000000000，在你看过一遍之后，它便消失在你面前，随后问题就出现了，给你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