#include<cstdio>
int n,m,i,j,b[16][100001];
#define N(x,y) y^((x^y)&-(x<y))
char u[0xBBAEE0];
unsigned int A()
{
    static unsigned int p=0x0;
    unsigned int number=0x0;
    for(u[p]>0x2F||++p;u[p]>0x2F;++p)
        number=number*0xA+u[p]-0x30;
    return number;
}
char v[0x7A1];
unsigned int p=~0x0;
void S(unsigned int x)
{
    unsigned int digits =
        x>0x1869F?0x7:
        x>0x270F?0x6:
        x>0x3E7?0x5:
        x>0x63?0x4:
        x>0x9?0x3:0x2;
    for(unsigned int i=digits;--i;x/=0xA)
        v[p+i]=x%0xA+0x30;
    v[p=p+digits]=0xA;
}
int main()
{
    freopen("rmq.in","r",stdin),freopen("rmq.out","w",stdout),fread(u,1,0xBBAEE0,stdin),n=A(),m=A()+0x1;
    for(i=0x1;i<=n;i++)
        b[0x0][i]=A();
	for(i=0x0;i<0x10;++i)
        for(j=0x1;j<n-i;++j)
        {
            int c=b[i][j],d=b[i][j+(0x1<<i)];
            b[i+0x1][j]=min(c,d);
        }
    for(int x,y,z,msb,c,d;--m;S(min(c,d)))
    {
        x=A(),y=A(),z=y-x+0x1,msb;
        asm("bsrl %1,%0":"=r"(msb):"r"(z));
        c=b[msb][x],d=b[msb][y+0x1-(0x1<<msb)];
    }
    fwrite(v,0x1,p,stdout);
}