Cod sursa(job #789234)
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;
const int N=100001;
int rmq[20][N],lg[N],v[N],n,m;
ifstream in ("rmq.in");
void read ()
{
in>>n>>m;
for(int i=1;i<=n;++i)
in>>v[i];
}
void solve ()
{
for(int i=2;i<=n;++i)
lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;++i)
rmq[0][i]=v[i];
for(int i=1;(1<<i)<=n;++i)
for(int j=1;j+(1<<i)<=n+1;++j)
{
int l=1<<(i-1);
rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+l]);
}
}
void out ()
{
freopen ("rmq.out","w",stdout);
for(int i=1,a,b,d,ad,l;i<=m;++i)
{
in>>a>>b;
d=b-a+1;
l=lg[d];
ad=d-(1<<l);
printf("%d\n",min(rmq[l][a],rmq[l][a+ad]));
}
}
int main ()
{
read ();
solve ();
out ();
return 0;
}