import java.io.*;

class Main{
    static int N = 200010, M = 18, n;
    static int[][] dp = new int[N][M];
    static int[] a;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void init(){
        for(int len = 0; len < M; len++){   
            for(int i = 1; i + (1 << len) - 1 <= n; i++){     //这里的右边界是i + (1 << len) - 1
                int j = len;
                if(len == 0) dp[i][j] = a[i];  //当2^0 = 1， 长度为1时， 最大值就是它本身
                else dp[i][j] = Math.max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
            }
        }
    }

    public static int query(int L, int R){
        int len = R - L + 1;
        int k =(int)( Math.log(len) / Math.log(2) );
        int res = Math.max(dp[L][k], dp[R - (1 << k) + 1][k]);
        return res;
    }

    public static void main(String[] args) throws Exception{
         n = Integer.valueOf(read.readLine());
         a = new int[n + 1];
         String[] ss = read.readLine().split(" ");
         for(int i = 1; i <= n; i++){
             a[i] = Integer.valueOf(ss[i - 1]);
         }
         int m = Integer.valueOf(read.readLine());
         init();
         while( m -- > 0){
             ss = read.readLine().split(" ");
             int L = Integer.valueOf(ss[0]);
             int R = Integer.valueOf(ss[1]);
             System.out.println(query(L, R));
         }

    }
}