#include <cstdio>
#define MaxN 100050
#define fs(x)     ((x)*2)
#define fd(x)     ((x)*2+1)

struct xd{
      long long a,b,c,d;
};

xd Arb[4*MaxN];

int N,M,Val,Pos,A,B,i,V[MaxN];
long long Max,Sum;

long long Maxim(long long a,long long b)
{
      if(a>b)
            return a;
      return b;
}

void Update(int nod,int st,int dr)
{
      if(st==dr && st==Pos)
      {
            Arb[nod].a=Arb[nod].b=Arb[nod].c=Arb[nod].d=Val;
            return;
      }
      int div=(st+dr)/2;
      if(div>=Pos)
            Update(fs(nod),st,div);
      else
            Update(fd(nod),div+1,dr);
      Arb[nod].a=Maxim(Arb[fs(nod)].a,Arb[fs(nod)].d+Arb[fd(nod)].a);
      Arb[nod].b=Maxim(Arb[fd(nod)].b,Arb[fs(nod)].b+Arb[fd(nod)].d);
      Arb[nod].c=Maxim( Maxim(Arb[fs(nod)].c,Arb[fd(nod)].c), Arb[fs(nod)].b+Arb[fd(nod)].a);
      Arb[nod].d=Arb[fs(nod)].d+Arb[fd(nod)].d;
}

void Query(int nod,int st,int dr)
{
      if(A<=st && dr<=B)
      {
            if(Sum<0)
                  Sum=0;
            Max=Maxim(Max, Maxim(Arb[nod].c,Sum+Arb[nod].a));
            Sum=Maxim(Sum+Arb[nod].d,Arb[nod].b);
            return;
      }
      int div=(st+dr)/2;
      if(A<=div)
            Query(fs(nod),st,div);
      if(div<B)
            Query(fd(nod),div+1,dr);
}

int main()
{
      freopen("sequencequery.in","r",stdin);
      freopen("sequencequery.out","w",stdout);
      scanf("%d%d",&N,&M);
      for(i=1;i<=N;i++)
      {
            scanf("%d",&V[i]);
            Val=V[i]; Pos=i;
            Update(1,1,N);
      }

      for(i=1;i<=M;i++)
      {
            scanf("%d%d",&A,&B);
            Max=V[A]; Sum=0;
            Query(1,1,N);
            printf("%lld\n",Max);
      }

      return 0;
}