Sparse Table

#include<bits/stdc++.h>
#define MAXN 100010
#define INF 1e9

using namespace std;

int n;
int arr[MAXN];
int sptable[20][MAXN];

void build() {
    for( int i = 0; i < n; i++ ) sptable[0][i] = i;

    for( int i = 1; (1 << i) <= n; i++ ) {
        for( int j = 0; j + ( 1 << i ) <= n; j++ ) {
            if (arr[sptable[i-1][j]] < arr[sptable[i-1][j + (1 << (i-1))]]){
                sptable[i][j] = sptable[i-1][j];
            }
            else {
                sptable[i][j] = sptable[i-1][j + (1 << (i-1))];
            }
        }
    }
}

int query( int l, int r ) {
    if(l > r) swap( r, l );
    int size = r - l + 1;
    int logOfSize = __builtin_clz(1) - __builtin_clz(size);
    return min( arr[sptable[logOfSize][l]], arr[sptable[logOfSize][r - (1 << logOfSize) + 1 ]] );
}
int main() {

    int q, l, r;

    scanf( "%d", &n );
    for( int i = 0; i < n; i++ ) {
        scanf( "%d", &arr[i] );

    }
    for(int i = 0; i < 20; i++) {
        // arr[i] = INF;
        for(int j = 0; j < n   ; j++) {
            sptable[i][j] = INF;
        }
    }
    build();
    scanf( "%d", &q );
    for( int i = 0; i < q; i++ ) {
        scanf("%d %d", &l, &r);
        printf("%d\n", query(l, r));
    }


    return 0;
}