#include <fstream>
#include <cmath>

using namespace std;

ifstream cin("rmq.in");
ofstream cout("rmq.out");

int v[100005];
int rmq[20][100005];
int n;

long long p2[20];
void put2()
{
    p2[0]=1;
    for(int i=1;i<=17;i++)
        p2[i]=p2[i-1]*2;
}

int cb(int x)
{
    int st=0, dr=17, sol=-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(p2[mij]<=x)
        {
            sol=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    return sol;
}

int main()
{
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        rmq[0][i]=v[i];
    }

    for(int exp=1; exp<=17; exp++)
    {
        for(int poz=1;poz<=n;poz++)
        {
            if(rmq[exp-1][poz]==0)
                rmq[exp][poz]=rmq[exp-1][min(n, poz+(1<<(exp-1)))];
            else if(rmq[exp-1][min(n, poz+(1<<(exp-1)))]==0)
                rmq[exp][poz]=rmq[exp-1][poz];
            else
                rmq[exp][poz]=min(rmq[exp-1][poz], rmq[exp-1][min(n, poz+(1<<(exp-1)))]);
        }
    }

    put2();
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        int p=cb(abs(a-b));
        cout<<min(rmq[p][min(a,b)], rmq[p][max(a,b)-((1<<p)-1)])<<'\n';
    }
    return 0;
}