#include <fstream>
#include <iostream>
#define oo 0x7fffffff
using namespace std;
class SegmentTree {
private:
int* v;
int* segTree;
int Size;
public:
SegmentTree(int Size) {
this->Size = Size;
v = new int[Size];
segTree = new int[4 * Size + 1];
}
void addNumber(int i, int x) {
v[i] = x;
}
void buildSegmentTree(int low, int high, int root) {
if(low == high)
segTree[root] = v[low];
else {
int mid = (low + high) >> 1;
buildSegmentTree(low, mid, 2 * root + 1);
buildSegmentTree(mid + 1, high, 2 * root + 2);
segTree[root] = min(segTree[2 * root + 1], segTree[2 * root + 2]);
}
}
void updateSegmentTree(int low, int high, int root, int X, int Y) {
// The value of the element X will become Y
if(low == high)
segTree[root] = Y;
else {
int mid = (low + high) >> 1;
if(X <= mid) // The index is in the left subtree
updateSegmentTree(low, mid, 2 * root + 1, X, Y);
else
updateSegmentTree(mid + 1, high, 2 * root + 2, X, Y);
segTree[root] = min(segTree[2 * root + 1], segTree[2 * root + 2]);
}
}
int RMQ(int low, int high, int root, int Begin, int End) {
if(Begin <= low && high <= End)
return segTree[root];
if(Begin > high || End < low)
return oo;
int mid = (low + high) >> 1;
return min(RMQ(low, mid, 2 * root + 1, Begin, End),
RMQ(mid + 1, high, 2 * root + 2, Begin, End));
}
~SegmentTree() {
delete[] v;
delete[] segTree;
}
};
int main() {
ifstream fin("rmq.in");
ofstream fout("rmq.out");
int n, m, x, y;
fin >> n >> m;
SegmentTree* sTree = new SegmentTree(n);
for(int i = 0; i < n; ++i) {
fin >> x;
sTree->addNumber(i, x);
}
sTree->buildSegmentTree(0, n - 1, 0);
for(int i = 0; i < m; ++i) {
fin >> x >> y;
fout << sTree->RMQ(0, n - 1, 0, x - 1, y - 1) << "\n";
}
delete sTree;
return 0;
}