#include <fstream>

using namespace std;


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

int rmq[100000][17];

void generateRMQ(int& n)
{
    for(int i=0; i<n; i++)
    {
        cin>>rmq[i][0]; //seteaza minimul pentru toate intervalele de lungime 2^0 = 1
    }
    for(int j=1; j<=18; j++)
    {
        for(int i=0; i+(1<<j)-1<n; i++)
        {
            rmq[i][j]=min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
            //cout<<i<<" "<<j<<": "<<rmq[i][j]<<"\n";
        }
    }
}

int main()
{
    int n, m;
    cin>>n>>m;

    generateRMQ(n);


    int st, dr;
    for(int i=0; i<m; i++)
    {
        cin>>st>>dr;
        dr--, st--;
        int dist=(dr-st)+1, pow2=0;

        while(dist>(1<<pow2))
            pow2++;
        pow2--;
        cout<<pow2<<" ";
        cout<<min(rmq[st][pow2], rmq[dr-(1<<pow2)+1][pow2])<<"\n";
    }
}