#include <iostream>
#include <fstream>
#define max 250005
using namespace std;
ifstream fin("cuburi2.in");
ofstream fout("cuburi2.out");

long long s[max],r[max],l[max],mx;
int n,m,x,y,i,nr,dr,st,mid,pos;
string str,rz;
int main() {
	
	fin>>n>>m;	
	getline(fin,str);
	getline(fin,str);
	str+=' ';
	mx=str.size();
	n=0;
	for(i=0;i<mx;i++)
	{
		if(str[i]!=' ')
		{
			nr=0;
			while(str[i]!=' ')
			{	nr=nr*10+(str[i]-'0');	i++;	}
			n++;
			r[n]=nr;
			s[n]=s[n-1]+r[n];
			l[n]=l[n-1]+n*r[n];
		}
	}
	for(i=n;i>=1;i--)
		r[i]=r[i+1]+r[i]*(n-i+1);
	
	while(m)
	{
		m--;
		fin>>x>>y;
		st=x;	dr=y;
		while(st<=dr)
		{
			mid=st+(dr-st)/2;
			if(s[mid]-s[x-1]>=s[y]-s[mid])
			{
				dr=mid-1;
				if(s[y]-s[mid-1]>s[mid-1]-s[x-1])	st=dr+1;
			}
			else	st=mid+1;
		}
		
		mx=r[x]-r[mid]-(n-mid+1)*(s[mid-1]-s[x-1])+l[y]-l[mid]-mid*(s[y]-s[mid]);
		if(s[mid]-s[x-1]<s[y]-s[mid]&&mid<y)
		{
			mx=mx+(s[mid]-s[x-1])-(s[y]-s[mid]);
			mid++;
		}
		str="";
		while(mx!=0)
		{	str+=(mx%10)+'0';	mx/=10;	}
		str+=" ";
		while(mid!=0)
		{	str+=(mid%10)+'0';	mid/=10; }
		rz="";
		for(i=int(str.size()-1);i>=0;i--)
			rz+=str[i];
		fout<<rz<<"\n";
	}
}