#include<fstream>
#include<algorithm>
#define L 30
#define INF 1000000
using namespace std;

class InputReader {
  private:
    static const int BUFF_SIZE = 1 << 17;
    FILE *f;
    int bp;
    char buff[BUFF_SIZE];
    inline void nxt() {
      if (++bp == BUFF_SIZE) {
        fread(buff, sizeof(char), BUFF_SIZE, f);
        bp = 0;
      }
    }
  public:
    InputReader (const char *file_name) {
      f = fopen(file_name, "r");
      bp = BUFF_SIZE - 1;
    }
    void close() {
      fclose(f);
    }
    InputReader& operator >> (int &num) {
      num = 0;
      while (isdigit(buff[bp]) == 0)
        nxt();
      while (isdigit(buff[bp])) {
        num = num * 10 + buff[bp] - '0';
        nxt();
      }
      return *this;
    }
} f("rmq.in");

class OutParser {
private:
    FILE *fout;
    char *buff;
    int sp;

    void write_ch(char ch) {
        if (sp == 50000) {
            fwrite(buff, 1, 50000, fout);
            sp = 0;
            buff[sp++] = ch;
        } else {
            buff[sp++] = ch;
        }
    }


public:
    OutParser(const char* name) {
        fout = fopen(name, "w");
        buff = new char[50000]();
        sp = 0;
    }
    ~OutParser() {
        fwrite(buff, 1, sp, fout);
        fclose(fout);
    }

    OutParser& operator << (int vu32) {
        if (vu32 <= 9) {
            write_ch(vu32 + '0');
        } else {
            (*this) << (vu32 / 10);
            write_ch(vu32 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (long long vu64) {
        if (vu64 <= 9) {
            write_ch(vu64 + '0');
        } else {
            (*this) << (vu64 / 10);
            write_ch(vu64 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (char ch) {
        write_ch(ch);
        return *this;
    }
    OutParser& operator << (const char *ch) {
        while (*ch) {
            write_ch(*ch);
            ++ch;
        }
        return *this;
    }
} g("rmq.out");

int v[100002],rmq[12][3335],N,p[32],e[3335],poz[100002],st[102],stare[100002],s[1002];

void calc()
{
    int i,x=2,k=1;
    while(x<=N)
    {
        for(i=1;i<=N-x+1;i++)
            rmq[k][i]=min(rmq[k-1][i],rmq[k-1][i+x/2]);
        x*=2;
        k++;
    }
}

void RMQ(int x,int y)
{
    int st,dr,sol=INF,k,z,mask;
    st=(x-1)/L+1;
    if((x-1)%L!=0)
        st++;
    dr=(y-1)/L+1;
    if(y%L!=0)
        dr--;
    if(st<=dr)
    {
        k=e[dr-st+1];
        z=p[k];
        sol=min(rmq[k][st],rmq[k][dr-z+1]);
    }
    if(dr-st>=-1)
    {
        if(y%L!=0)
            sol=min(sol,v[poz[y]]);
        if((x-1)%L!=0)
            y=x-x%L+L*(x%L!=0);
        else
            y=x-1;
    }
    if(x<=y)
    {
        mask=stare[y]/p[(x-1)%L];
        mask=mask&(-mask);
        sol=min(sol,v[x+s[mask%1000]]);
    }
    g<<sol<<'\n';
}

int main()
{
    int n,m,k=0,minim=INF,x=1,y,vf=0,i;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>v[i];
        k++;
        minim=min(minim,v[i]);
        if(k==L)
            rmq[0][++N]=minim,k=0,minim=INF;
    }
    p[0]=1;
    s[p[0]]=0;
    for(i=1;i<=L;i++)
        p[i]=p[i-1]*2,s[p[i]%1000]=i;
    k=0;
    for(i=1;i<=N;i++)
    {
        if(x*2==i)
            x*=2,k++;
        e[i]=k;
    }
    calc();
    k=0;
    x=0;
    y=0;
    for(i=1;i<=n;i++)
    {
        k++;
        while(vf>=1&&v[st[vf]]>=v[i])
        {
            x^=p[(i-1)%L-(st[vf]-1)%L];
            y^=p[(st[vf]-1)%L];
            vf--;
        }
        st[++vf]=i;
        x*=2;
        x++;
        y+=p[(i-1)%L];
        stare[i]=y;
        poz[i]=st[1];
        if(k==L)
        {
            k=0;
            x=0;
            vf=0;
            y=0;
        }
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        if(i==72)
            i++,i--;
        RMQ(x,y);
    }
    return 0;
}