//Solutie cu arbori de intervale
#include <fstream>
 
using namespace std;
 
#define inf 10000000005ll
 
struct nod
{
   int st,dr;
    
   //minimul,maximul si diferenta maxima cu min<max (ca pozitie)
   long long min,max,d;   
    
   nod()
   {
      st=0;
      dr=0;
      d=-inf;
      min=inf;
      max=-inf;    
   }  
}arb[262144];
 
long long int v[100005];
 
inline long long int minim(long long int a,long long int b)
{
   if(a<b)
     return a;
   return b;    
}
 
inline long long int maxim(long long int a,long long int b)
{
   if(a>b)
     return a;
   return b;    
}
 
inline long long int maxim(long long int a,long long int b,long long int c)
{
   return maxim(maxim(a,b),c);    
}
 
void build(int st,int dr,int poz)
{
    arb[poz].st=st;
    arb[poz].dr=dr;
     
    if(st==dr)
    {
       arb[poz].min=v[st];
       arb[poz].max=v[st];
       arb[poz].d=-inf;         
    }   
    else
    {
       int mijl=(st+dr)>>1;
       build(st,mijl,poz<<1);
       build(mijl+1,dr,(poz<<1)+1);
       arb[poz].min=minim(arb[poz<<1].min,arb[(poz<<1)+1].min);
       arb[poz].max=maxim(arb[poz<<1].max,arb[(poz<<1)+1].max);
       //Asa se calculeaza diferenta maxima:
       //maximul dintre
       //subarborele stang + drept
       // si
       //difereta dintre maximul din dreapta si minimul din stanga
       arb[poz].d=maxim(arb[poz<<1].d,arb[(poz<<1)+1].d,(arb[(poz<<1)+1].max-arb[poz<<1].min));   
    }
}
 
//Minim pe interval
long long int query_min(int st,int dr,int poz)
{
   if(arb[poz].st==st && arb[poz].dr==dr)
      return arb[poz].min;                  
   else
   {
      int mijl=(arb[poz].st+arb[poz].dr)>>1;
      if(dr<=mijl)
        return query_min(st,dr,poz<<1);
      if(st>mijl)
        return query_min(st,dr,(poz<<1)+1);
      return minim(query_min(st,mijl,poz<<1),query_min(mijl+1,dr,(poz<<1)+1));   
   }
}
 
//Maxim pe interval
long long int query_max(int st,int dr,int poz)
{
   if(arb[poz].st==st && arb[poz].dr==dr)
      return arb[poz].max;                  
   else
   {
      int mijl=(arb[poz].st+arb[poz].dr)>>1;
      if(dr<=mijl)
        return query_max(st,dr,poz<<1);
      if(st>mijl)
        return query_max(st,dr,(poz<<1)+1);
      return maxim(query_max(st,mijl,poz<<1),query_max(mijl+1,dr,(poz<<1)+1));   
   }
}
 
//Diferenta maxima pe interval
long long int query(int st,int dr,int poz)
{
   if(arb[poz].st==st && arb[poz].dr==dr)
      return arb[poz].d;                  
   else
   {
      int mijl=(arb[poz].st+arb[poz].dr)>>1;
      if(dr<=mijl)
        return query(st,dr,poz<<1);
      if(st>mijl)
        return query(st,dr,(poz<<1)+1);
      //Stanga, dreapta si diferenta dintre maximul din dreapta si minimul din stanga
      return maxim(query(st,mijl,poz<<1),query(mijl+1,dr,(poz<<1)+1),query_max(mijl+1,dr,(poz<<1)+1)-query_min(st,mijl,poz<<1));   
   }
}
 
int main()
{
    ifstream cin("sequencequery.in");
    ofstream cout("sequencequery.out");
     
    int n,m,i,x,y;
    cin>>n>>m;
     
    //Facem minime si maxime pe sume partiale
    for(i=1;i<=n;i++)
     cin>>v[i],v[i]+=v[i-1];
     
    //Construim arborele
    build(0,n,1);
     
    for(i=0;i<m;i++)
    {
       cin>>x>>y;
       cout<<query(x-1,y,1)<<'\n';               
    }
     
    cin.close();
    cout.close();
    //system("PAUSE");
    return 0;
}