SPARSE TABLE RANGE MINIMUM QUERY

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

#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define nl "\n"
#define pp pair < ll , ll >
#define sz(x) (ll)x.size()
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;

const double EPS = 1e-12;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;

ll n , a[N],sparse[N][20],k;
//using sparse table
 ll query(ll l ,ll r){
   ll j = log2(r - l  + 1);
   return min(sparse[l][j],sparse[r-(1 << j) + 1][j]);
  /* // elements taken = 2^j from l;
   bache hue  = r - l + 1 - 2^j;
   utna aage l ko srka dete hn to l + r - l + 1 - 2^j
   to iska mtlb r - 2^j + 1 s 2^j elements*/

 }

int main()
{
    fast;
    cin >> n ;
    for(int i = 0 ; i  < n ; i++ )
      cin >> a[i];
   k = log2(n) + 1;
   /*yahan p k ko itna isliye liye gya h maan ko n = 6 h to k ki value yahan p 3 aa jayegi
   agr jyada le lete to 2^3 wo 8 ho jata itne elements hmare paaad nhi h
   so k >= log2(n) + 1;*/

   for(int i = 0 ; i < n ; i++ ){
      sparse[i][0] = a[i];
   }
   for(int j = 1 ; j  < k ; j++ ){
      for(int i = 0 ; i + (1 << j) - 1 < n ; i++ ){
         sparse[i][j] = min(sparse[i][j-1],sparse[i+(1 << (j-1))][j-1]);
      }
   }
   /*is step ko smjhne k liye maan lo hmne 2^2 ko 2^1 aur 2^1 k baag m thod diya h
   to understand take six elements and make the sparse table */

   /*for(int j = 0 ; j  < k ; j++ ){
      for(int i = 0 ; i + (1 << j) - 1 < n ; i++ ){
        cout << sparse[i][j] << " ";
      }
      cout << "\n";
   }*/
   ll q;
   cin >> q;
   while(q--){
      ll l , r;
      cin >> l >> r ;
     // l--,r--;
      cout << query(l,r) << "\n";
   }
   //build time O(nlog(n))
   //query time O(1)
   //query time for sum query is log2(n)
   //that is most important























    return 0;

}