Sparse Table

n = int(input())
A = list(map(int, input().split()))
W = [0] * (n + 1)

for a in range(2, n + 1):
    W[a] = W[a // 2] + 1

l = W[n] + 1
P = [0] * l
P[0] = 1
for i in range(1, l):
    P[i] = P[i - 1] * 2

S = [[0] * l for _ in range(n)]
for a in range(n):
    S[a][0] = A[a]

for i in range(1, l):
    for a in range(n - P[i] + 1):
        S[a][i] = min(S[a][i - 1], S[a + P[i - 1]][i - 1])

m = int(input())
for _ in range(m):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    k = W[r - l + 1]
    print(min(S[l][k], S[r - P[k] + 1][k]), end=" ")

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    
    vector<int> W(n + 1, 0);
    for (int a = 2; a <= n; a++) {
        W[a] = W[a / 2] + 1;
    }
    
    int l = W[n] + 1;
    vector<int> P(l, 0);
    P[0] = 1;
    for (int i = 1; i < l; i++) {
        P[i] = P[i - 1] * 2;
    }
    
    vector<vector<int>> S(n, vector<int>(l, 0));
    for (int a = 0; a < n; a++) {
        S[a][0] = A[a];
    }
    
    for (int i = 1; i < l; i++) {
        for (int a = 0; a < n - P[i] + 1; a++) {
            S[a][i] = min(S[a][i - 1], S[a + P[i - 1]][i - 1]);
        }
    }
    
    int m;
    cin >> m;
    for (int _ = 0; _ < m; _++) {
        int left, right;
        cin >> left >> right;
        left--;
        right--;
        int k = W[right - left + 1];
        cout << min(S[left][k], S[right - P[k] + 1][k]) << " ";
    }
    
    return 0;
}