#include<fstream>
using namespace std;
int tree[4*100001+50],treemin[4*100001+50],val,poz,tmaxim,tminim,start,finish,poz1,poz2,poz3,poz4;
int maxim(int a,int b)
{if(a<b) return b;
return a;
    }
int minim(int a,int b)
{if(a<b) return a;
return b;
    
    }    
void update(int nod, int st,int dr)
{if(st==dr) {tree[nod]=val;return;}
int m=(st+dr)/2;
if(poz<=m) update(2*nod,st,m);
else update(2*nod+1,m+1,dr);
tree[nod]=max(tree[2*nod],tree[2*nod+1]);     
     
     }

void query(int nod,int st,int dr)
      {if(start<=st && dr<=finish) {if(tmaxim<tree[nod]) {tmaxim=tree[nod];}return ;}
      int m=(st+dr)/2;
      if(start<=m) query(2*nod,st,m);
      if(m<finish) query(2*nod+1,m+1,dr);
      
              
              }
void updatemin(int nod,int st,int dr)
{if(st==dr) {treemin[nod]=val;return;}
  int m=(st+dr)/2;
  if(poz<=m) updatemin(2*nod,st,m);
  else updatemin(2*nod+1,m+1,dr);
  treemin[nod]=maxim(treemin[2*nod],treemin[2*nod+1]);   
     }              
void querymin(int nod,int st,int dr)
 {if(start<=st && dr<=finish) {if(tminim<treemin[nod]) {tminim=treemin[nod];}return;}
   int m=(st+dr)/2;
   if(start<=m) querymin(2*nod,st,m);
   if(m<finish) querymin(2*nod+1,m+1,dr); 
     
     }  
     
int main()
{freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
int n,m,x,s[100001];
scanf("%d %d",&n,&m);
s[0]=0;
for(int i=1;i<=n;i++) {scanf("%d",&x); s[i]=x+s[i-1];val=s[i];poz=i;update(1,1,n);val=-s[i];poz=i;updatemin(1,1,n);}
for(;m;m--) {scanf("%d %d",&start,&finish);
                if(start==finish) {printf("%d \n",s[start]-s[start-1]);}
          else{             tmaxim=-100000;tminim=-100000;start--;
                 query(1,1,n);querymin(1,1,n);
            printf("%d \n",tmaxim+tminim);}
            }
    
    
    return 0;}