sparse_table.cpp

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

const int MAX_N = 100'005;
const int LOG = 17;
int a[MAX_N];
int a[MAX_N][LOG];


int query(int L, int R) {
	int length = R - L + 1;
	int k = 0;
	while((1 << (k + 1)) <= length) {
		k++;
		 // can als0 31 -  use __builtin_clz
	}
	return min(m[L][K] , M[R - (1 << k) + 1][k]);
}

int main() {
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		m[i][0] = a[i];
	}

	//  // also 
	// for(int i = 2 ; i <= length ; i++)
	// {
	// 	log[i] = log[i / 2] + 1;
	// }
	for(int k = 1 ; k < LOG ; k++) {
		for(int i = 0; i + (1 << k) - 1 < n; i++) {
			m[i][k] = min(m[i][k] , m[i + (1 << (k - 1))][k - 1]);

		}
	}
	int q;
	cin >> q;
	for(int i = 0; i < q; i++) {
		int L, R;
		cin >> L >> R;
		cout << query(L, R) << '\n';

	}
}