Cod sursa(job #820229)
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
const int N = 100001;
int lg[N], v[N], RMQ[20][N];
int n, m, k;
int main()
{
fin >> n >> m;
for( int i = 1; i <= n; ++i )
{
fin >> v[i];
RMQ[0][i] = v[i];
}
k = floor(log(n)/log(2));
for( int i = 1; i <= k; ++i )
for( int j = 1; j + (1 << i) <= n+1; ++j )
{
RMQ[i][j] = min( RMQ[i-1][j], RMQ[i-1][j+( 1 <<( i-1 ) )] );
}
for( int i = 2; i <= n; ++i )
lg[i] = 1 + lg[i/2];
int a, b, l, d, ad;
for( int i = 1; i <= m; ++i )
{
fin >> a >> b;
d = b - a + 1;
l = lg[d];
ad = d - (1 << l);
fout << min( RMQ[l][a], RMQ[l][a+ad] ) << '\n';
}
fin.close();
fout.close();
return 0;
}