#include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<math.h>

 using namespace std;

 const int maxn=1e5+;

 const int maxl=;

 int ma[maxn][maxl];

 int st[maxn][maxl];

 int a[maxn],prelog[maxn];

 void initRMQ(int n){

     for(int i=;i<=n;++i){

         prelog[i]=prelog[i-];

         if((i&(-i))==i)prelog[i]++;

     }

     for(int i=;i<=n;++i)ma[i][]=a[i];

     for(int j=;(<<j)<=n;++j){

         for(int i=;i+(<<j)-<=n;++i){

             ma[i][j]=max(ma[i][j-],ma[i+(<<j-)][j-]);

         }

     }

 }

 int askRMQ(int l,int r){

     if(l>r)swap(l,r);

     int k=prelog[r-l+];

     return max(ma[l][k],ma[r-(<<k)+][k]);

 }

 void initST(int n){

     for(int i=;i<=n;++i){

         prelog[i]=prelog[i-];

         if((<<prelog[i]+)==i)++prelog[i];

     }

     for(int i=;i<n;++i)st[i][]=a[i];

     for(int i=n-;i>=;--i){

         for(int j=;i+(<<j)-<n;++j){

             st[i][j]=max(st[i][j-],st[i+(<<j-)][j-]);

         }

     }

 }

 int askST(int l,int r){

     if(l>r)swap(l,r);

     int k=prelog[r-l+];

     return max(st[l][k],st[r-(<<k)+][k]);

 }