#include <fstream>
using namespace std;
ifstream f ("sequencequery.in");
ofstream g ("sequencequery.out");
const int nmax=1e5+3;
int arb1[4*nmax],arb2[4*nmax],val,poz,a,b,usu1,usu2,n,m,v[nmax],sol,vv[nmax];
void update1(int st,int dr,int nod)
{
      if(st==dr)
      {
            arb1[nod]=val;
            return;
      }
      int mij=(st+dr)/2;
      if(poz<=mij) update1(st,mij,2*nod);
      else update1(mij+1,dr,2*nod+1);
      arb1[nod]=min(arb1[2*nod],arb1[2*nod+1]);
}
void update2(int st,int dr,int nod)
{
      if(st==dr)
      {
            arb2[nod]=val;
            return;
      }
      int mij=(st+dr)/2;
      if(poz<=mij) update2(st,mij,2*nod);
      else update2(mij+1,dr,2*nod+1);
      arb2[nod]=max(arb2[2*nod],arb2[2*nod+1]);
}
void query1(int st,int dr,int nod)
{
      if(a<=st&&dr<=b)
      {
            usu1=min(usu1,arb1[nod]);
            return;
      }
      int mij=(st+dr)/2;
      if(a<=mij) query1(st,mij,2*nod);
      if(b>mij) query1(mij+1,dr,2*nod+1);
}
void query2(int st,int dr,int nod)
{
      if(a<=st&&dr<=b)
      {
            usu2=max(usu2,arb2[nod]);
            return;
      }
      int mij=(st+dr)/2;
      if(a<=mij) query2(st,mij,2*nod);
      if(b>mij) query2(mij+1,dr,2*nod+1);
}
int main()
{
      f>>n>>m;
      for(int i=1;i<=4*n;++i)
      {
            arb1[i]=2e9;
            arb2[i]=-2e9;
      }
      for(int i=1;i<=n;++i)
      {
            f>>vv[i];
            v[i]=vv[i]+v[i-1];
            poz=i;
            val=v[i];
            update1(1,n,1);
            update2(1,n,1);
      }
      while(m--)
      {
            f>>a>>b;
            if(a==b)
            {
                  g<<vv[a]<<'\n';
                  continue;
            }
            usu1=2e9;
            query1(1,n,1);
            usu2=-2e9;
            query2(1,n,1);
            sol=usu2-usu1;
            g<<sol<<'\n';
      }
      return 0;
}