Sparse Table

#include<bits/stdc++.h>

using namespace std;


typedef  long long ll;

const ll Max=1e5;


ll P[Max][20];

void buildSparseTable(ll ara[], ll n)
{
    ll a,b;

       for(ll i=0; i<n; i++)
        P[i][0]=ara[i];

        for(ll j=1; (1<<j)<=n; j++)
        {
            for(ll i=0; (i+(1<<j)-1) <n; i++)
            {
               a=P[i][j-1];

               b=P[i+(1<< (j-1))][j-1];

               P[i][j]=min(a,b);
            }
        }


}

ll queury(ll L,ll R)
{
    ll k=log2(R-L+1);


    return min(P[L][k],P[R-(1<<k)+1][k]);

}
int main()
{
   ll n;

   cin>>n;

   ll ara[n+1];

   for(ll i=0; i<n; i++)
   {
       cin>>ara[i];
   }

   buildSparseTable(ara,n);

   ll q,l,r;
   cin>>q;


   while(q--)
   {

       cin>>l>>r;

       cout<<queury(l,r)<<endl;
   }
}