import java.util.*;
import java.io.*;
/**
* f[i][j]表示以i开头长度为2^j次方范围的最大值
* 对于a数组
* 初始化f数组：j == 0时，f[i][j] = a[i]
               j != 0时，f[i][j] = f[i][j - 1] 和f[i + (1 << j - 1)][j - 1]//将区间二分求解两个区间的最大值
  查询a[l, r]的最大值：
  找到区间长度r - l + 1 = len的最小2^k使得2^k <= len
  f[l][k]左边最大值
  f[r - (1 << k) + 1][r]右边最大值，虽然可能会有重合但是不影响求解最大值

  2^k <= len, 求解k：
  两边去log2：k <= log2(len)
  换底公式k <= log10(len) / log10(2)下取整就是最大的k
*/
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);
    static final int N = 200010, M = 18;
    static int[] a = new int[N];
    static int[][] f = new int[N][M];
    static int n, m;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());

        String[] s = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(s[i - 1]);
        init();

        m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            String[] str = br.readLine().split(" ");
            int res = query(Integer.parseInt(str[0]), Integer.parseInt(str[1]));
            out.println(res);
        }

        out.flush();
    }

    static int query(int l, int r) {
        int len = r - l + 1;
        int k = (int)(Math.log10(len) / Math.log10(2));
        return Math.max(f[l][k], f[r - (1 << k) + 1][k]);
    }

    static void init() {
        for (int j = 0; j < M; j++) 
            for (int i = 1; i + (1 << j) - 1 <= n; i++) 
                if (j == 0) f[i][j] = a[i];
                else f[i][j] = Math.max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
    }
}