#include <cstdio>

#define MAXN 100000
#define INF 100000000000

using namespace std;

long long ssm[4*MAXN+5], s[4*MAXN+5], sufix[4*MAXN+5], prefix[4*MAXN+5];

long long ssm1, ssm2;
int a, b;

inline long long maxim( long long x, long long y )
{
  if( x<y )
    x=y;

  return x;
}

void update( int p, int st, int dr )
{
  int mid=(st+dr)/2;

  if( st==dr )
    ssm[p]=s[p]=sufix[p]=prefix[p]=b;
  else
  {
    if( a<=mid )
      update(2*p,st,mid);
    else
      update(2*p+1,mid+1,dr);

    ssm[p]=maxim(ssm[2*p],ssm[2*p+1]);
    ssm[p]=maxim(ssm[p],sufix[2*p]+prefix[2*p+1]);
    s[p]=s[2*p]+s[2*p+1];
    sufix[p]=maxim(sufix[2*p+1],s[2*p+1]+sufix[2*p]);
    prefix[p]=maxim(prefix[2*p],s[2*p]+prefix[2*p+1]);
  }
}

void query( int p, int st, int dr )
{
  int mid=(st+dr)/2;

  if( a<=st && dr<=b )
  {
    ssm1=maxim(ssm1,ssm2+prefix[p]);
    ssm1=maxim(ssm1,ssm[p]);
    ssm2=maxim(sufix[p],ssm2+s[p]);
    ssm2=maxim(ssm2,0);
  }
  else
  {
    if( a<=mid )
      query(2*p,st,mid);

    if( mid<b )
      query(2*p+1,mid+1,dr);
  }
}

int main()
{
  freopen( "sequencequery.in", "r", stdin );
  freopen( "sequencequery.out", "w", stdout );

  int n, m, x, y;

  scanf( "%d%d", &n, &m );

  for( int i=1;i<=n;i++ )
  {
    scanf( "%d", &x );

    a=i;
    b=x;

    update(1,1,n);
  }

  for( int i=1;i<=m;i++ )
  {
    scanf( "%d%d", &x, &y );

    a=x;
    b=y;

    ssm1=-INF;
    ssm2=0;

    query(1,1,n);

    printf( "%lld\n", ssm1 );
  }

  return 0;
}