给你一大串数字（编号为1到 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