#include <bits/stdc++.h>

 #define MAXN 10010

 using namespace std;

 int dp[MAXN][], a[MAXN]; //dp[i][j]存储从下标i开始,长度为2^j区间的最大值

 int main(void){

     int n;

     scanf("%d", &n);

     for(int i=; i<n; i++){

         scanf("%d", &a[i]);

         dp[i][]=a[i];    //dp初始化

     }

     int len=log2(n);

     for(int j=; j<=len; j++){ //长度为2^j的区间最大值可以由相邻的两个长度为2^(j-1)的区间合成

         for(int i=; i<n; i++){

             if(i+(<<j)<=n){

                 dp[i][j]=max(dp[i][j-], dp[i+(<<(j-))][j-]); //从相邻两个区间中选取最大值

             }

         }

     }

     int m;

     scanf("%d", &m);

     while(m--){

         int s, e;

         scanf("%d%d", &s, &e);

         int cnt=log2(e-s+);

         cout << max(dp[s][cnt], dp[e-(<<cnt)+][cnt]) << endl;

     }

     return ;

 }