#include<bits/stdc++.h>
#define ll long long int
#define N 100001
using namespace std;
string z="sequencequery.";
ifstream f(z+"in");
ofstream g(z+"out");

ll A[4*N],B[4*N],x,y,n,m,t=1,i,M,P;

ll QM(int p,int l,int r)
{
    if (x<=l&&r<=y)
        {
        if (A[p]>M)
            M=A[p],P=r;
        return A[p];
        }
    if (y<l||r<x)return -N;
    return max(QM(p*2,l,(l+r)/2),QM(p*2+1,(l+r)/2+1,r));
}ll Qm(int p,int l,int r)
{
    if (x-1<=l&&r<=P)
        {if (l!=1)
            return B[p];
        else return min(B[p],0ll);}
    if (P<l||r<x-1)return N;
    return min(Qm(p*2,l,(l+r)/2),Qm(p*2+1,(l+r)/2+1,r));
}

int main()
{
f>>n>>m;
while(t<n)t*=2;
for(i=0;i<n;++i)f>>A[t+i],B[t+i]=A[t+i]+=A[t+i-1];
for(;i<=t;++i)A[t+i]=-N+A[t-i-1],B[t+i]=N+B[t-i-1];
for(i=t-1;i;--i)A[i]=max(A[i*2],A[i*2+1]);
for(i=t-1;i;--i)B[i]=min(B[i*2],B[i*2+1]);
while(m--)
{
    f>>x>>y;
    M=-N,P=0;
    if (x!=y)g<<-Qm(1,1,t)+QM(1,1,t);
    else if (x!=1)g<<A[x+t-1]-A[x+t-2];
    else g<<A[x+t-1];
    g<<'\n';
}



return 0;
}