#include <iostream>
#include <algorithm>
#include <cstring> using namespace std;
const int maxn = + ;
int a[maxn];
int f[maxn][]; void rmq(int cnt){
memset(f, , sizeof(f));
for (int i = ; i <= cnt; i++){
f[i][] = a[i];
} //O(nlogn)
for (int j = ; j < ; j++){
for (int i = ; i <= cnt; i++){
if (i + ( << j) - <= cnt){
f[i][j] = max(f[i][j - ], f[i + ( << (j - ))][j - ]);
}
}
}
} int Query(int x, int y){
int k = ;
while (( << (k + )) <= y - x + )
k++;
return max(f[x][k], f[y - ( << k) + ][k]);
} int main(){
ios::sync_with_stdio(false); int n;
cin >> n;
for (int i = ; i <= n; i++){
cin >> a[i];
}
rmq(n);
int m;
cin >> m;
while (m--){
int x, y;
cin >> x >> y;
x++, y++;
int ans = Query(x, y);
cout << ans << endl;
} //system("pause");
return ;
}