#include <iostream>
#include <fstream>

using namespace std;

#define nmax 250005
#define inf (1LL<<50)

ifstream f("cuburi2.in");
ofstream g("cuburi2.out");

int n, m, high[nmax];
typedef struct{
    long long cost;
    long long cnt;
}camp;
camp st[nmax], dr[nmax];

void citeste(){

    f >> n >> m;
    for(int i=1; i<=n; i++) f >> high[i];

}

inline pair<int, long long> cb(int x, int y){
    int St = x; int Dr = y;
    while(St <= Dr){
        int mij = (St + Dr ) >> 1;
        long long stMij = st[mij].cost - st[x].cost - (1LL*(mij-x)*st[x-1].cnt);
        long long drMij = dr[mij].cost - dr[y].cost - (1LL*(y-mij)*dr[y+1].cnt);
        int prec = mij - 1;
        long long stPrec = st[prec].cost - st[x].cost - (1LL*(prec-x)*st[x-1].cnt);
        long long drPrec = dr[prec].cost - dr[y].cost - (1LL*(y-prec)*dr[y+1].cnt);
        if (mij == x) stPrec = inf, drPrec = inf;

        int next = mij + 1;
        long long stNext = st[next].cost - st[x].cost - (1LL*(next-x)*st[x-1].cnt);
        long long drNext = dr[next].cost - dr[y].cost - (1LL*(y-next)*dr[y+1].cnt);
        if (mij == y) stNext = inf, drNext = inf;
        if ( stPrec+drPrec >= stMij + drMij && stMij+drMij <= stNext+drNext ){// mij e pct cautat
            return make_pair(mij, stMij+drMij);
        }else if (stPrec+drPrec >= stMij + drMij && stMij+drMij >= stNext+drNext) {
            St = mij+1;
        }else Dr = mij-1;
    }
}

void rezolva(){

    //st[i].cost = costul de a muta toate cuburile din partea stanga a cubului i pe cubul i
    //st[i].cnt = numarul de cuburi pana la cubul i(inclusiv)
    //dr[i].cost/dr[i].cnt la fel...;

    st[1].cost = 0LL;
    st[1].cnt = 1LL*high[1];
    for(int i=2; i<=n; i++){
        st[i].cost = st[i-1].cost + st[i-1].cnt;
        st[i].cnt = st[i-1].cnt + 1LL*high[i];
    }

    dr[n].cost = 0LL;
    dr[n].cnt = 1LL*high[n];
    for(int i=n-1; i>=1; i--){
        dr[i].cost = dr[i+1].cost + dr[i+1].cnt;
        dr[i].cnt = dr[i+1].cnt + 1LL*high[i];
    }

    //pentru un interval [x,y] ma intereseaza care element are MIN( (st[i].cost - st[x].cost - (i-x)*st[x-1]) + (dr[i].cost - dr[y].cost - (y-i)*dr[y+1]cnt) ), cu i = x,y;
    // costurile astea au o proprietatea : in sirul format exista un elemnt care schimba monotonia : fie X acel element => toate element din [st, X] sunt descrescator, iar [X, Dr] sunt crescatoare => pot face o cautare binara
    for(int i=1; i<=m; i++){
        int x,y;
        f >> x >> y;
        /*
        long long rez = inf;
        int poz = 0;
        int v[y-x+4]; for(int i=0; i<y-x+4; ++i) v[i] = 0;
        for(int i=x; i<=y; i++){
            long long _st = st[i].cost - st[x].cost - (1LL*(i-x)*st[x-1].cnt);
            long long _dr = dr[i].cost - dr[y].cost - (1LL*(y-i)*dr[y+1].cnt);
            v[++v[0]] = _st + _dr;
            if (rez > _st+_dr){
                rez = _st + _dr;
                poz = i;
            }
        }

        int cnt = 0;
        for(int i=2; i<v[0]; ++i) if (v[i] < v[i-1] && v[i] < v[i+1]) ++cnt;
        g << max(1, cnt) << "\n";
        //cout << "\n";
        */
        pair<int, long long> X = cb(x, y);
        g << X.first << " " << X.second << "\n";
        //g << poz << " " << rez << "\n";
        //g << "\n";
    }


}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}