#include<stdio.h>
#include<ctype.h>
FILE *f = fopen("cuburi2.in","r");
FILE *g = fopen("cuburi2.out","w");
#define MaxN 250100
#define INF 1LL<<58;
#define ll long long
#define formula (ll)(Best_S[i]-(i-x+1)*B_S[x]-Best_S[x-1]+Best_D[i]-(y-i+1)*B_D[y]-Best_D[y+1])
#define MaxS 8*MaxN
int N,M,Poz,a,b;
ll Sol;
int A[MaxN];
char S[MaxS];
ll B_S[MaxN],B_D[MaxN],Best_S[MaxN],Best_D[MaxN];
void citire(void)
{
fscanf(f,"%d %d\n",&N,&M);
fgets(S,sizeof(S),f);
for(int i=0;S[i];i++)
if(isdigit(S[i]))
for(++A[0];isdigit(S[i]);A[A[0]] = A[A[0]]*10+S[i++]-'0');
A[0] = 0;
}
void Afisare(int A[])
{
for(int i=1;i<=N;i++)
printf("%d ",A[i]);
printf("\n");
}
void Preprocesare(void)
{
for(int i=1;i<=N;i++)
B_S[i] = B_S[i-1]+A[i-1];
for(int i=1;i<=N;i++)
Best_S[i] = Best_S[i-1]+B_S[i];
for(int i=N;i;i--)
B_D[i] = B_D[i+1]+A[i+1];
for(int i=N;i;i--)
Best_D[i] = Best_D[i+1]+B_D[i];
}
inline ll min(ll a,ll b)
{
return a < b ? a : b;
}
inline ll Min(int i,int x,int y)
{
return formula;
}
inline int CautBin(int li,int ls)
{
//printf("%d %d\n",li,ls);
if(ls-li+1 <= 4)
{
Poz = li;
for(li++;li<=ls;li++)
if(Min(Poz,a,b) > Min(li,a,b))
Poz = li;
return Poz;
}
if(Min(li,a,b) > Min(li+(ls-li)/3,a,b) && Min(li+(ls-li)/3,a,b) > Min(li+(ls-li)/3*2,a,b))
return CautBin(li+(ls-li)/3,ls);
else
return CautBin(li,li+(ls-li)/3*2);
}
void Rezolvare(void)
{
Preprocesare();
for(int i=1;i<=M;i++)
{
fscanf(f,"%d %d",&a,&b);
Poz = CautBin(a,b);
fprintf(g,"%d %lld\n",Poz,Min(Poz,a,b));
}
}
int main()
{
citire();
Rezolvare();
}