#include <cstdio>
#include <vector>
#define LengthMax 16*1024
#define LevelMax 14

using namespace std;

int v[LevelMax][LengthMax];

void read(int&q) {
    int i,length,newElem;
    scanf("%d%d",&length,&q);
    for(i=0;i<length;++i) {
        scanf("%d",&newElem);
        v[0][newElem]=newElem;
    }
}

int takeMin(int x,int y) {
    if(x==0&&y==0) {
        return 0;
    }
    if(x==0||y==0) {
        return x+y;
    }
    return (x<y)*(x-y)+y;
}

void formL(int l) {
    int i,n;
    n=LengthMax>>l;
    for(i=1;i<n;++i) {
        v[l][i]=takeMin(v[l-1][i+i-1],v[l-1][i+i]);
    }
}

void form() {
    int i;
    for(i=1;i<LevelMax;++i) {
        formL(i);
    }
}

int value(int l,int pos,int x1,int x2) {
    int y1,y,y2;
    y1=(pos-1)<<l;
    y2=pos<<l;
    if(x1==y1+1&&x2==y2) {
        return v[l][pos];
    }
    y=(y1+y2)>>1;
    if(x2<=y) {
        return value(l-1,(pos<<1)-1,x1,x2);
    }
    if(x1>y) {
        return value(l-1,(pos<<1),x1,x2);
    }
    return takeMin(value(l-1,(pos<<1)-1,x1,y),value(l-1,(pos<<1),y+1,x2));
}

void solve() {
    int x1,x2;
    scanf("%d%d",&x1,&x2);
    printf("%d\n",value(LevelMax,1,x1,x2));
}

int main()
{
    freopen("rmq.in","r",stdin);
    freopen("rmq.out","w",stdout);
    int q,iq;
    read(q);
    form();
    for(iq=0;iq<q;++iq) {
        solve();
    }
    return 0;
}