#include <fstream>
#include <cmath>
#define NMax 100005
#define LogMax 20

using namespace std;

ifstream fin("rmq.in");
ofstream fout("rmq.out");

int N,M;
int X[NMax];
int RMQ[LogMax][NMax];

void ReadArray()
{
    fin>>N>>M;
    for(int i=1;i<=N;i++)
        fin>>X[i];
}

void Precalculate()
{
    for(int i=1;i<=N;i++)
        RMQ[0][i] = X[i];
    for(int i = 1; (1<<i)<=N ;i++)
        {
            for(int j = 1;j <= N - (1<<i) + 1;j++)
                RMQ[i][j] = min(RMQ[i-1][j], RMQ[i-1][j+(1<<(i-1))]);
        }
}

int Query(int x, int y)
{
    int Length = y-x+1;
    int k = log2(Length);
    return min(RMQ[k][x],RMQ[k][y-(1<<k)+1]);
}

void SolveandPrint()
{
     while(M--)
    {
        int x,y;
        fin>>x>>y;
        fout<<Query(x,y);
    }
}

int main()
{

    ReadArray();

    Precalculate();

    SolveandPrint();

    return 0;
}