#include <bits/stdc++.h>
#define maxn 100000
#define maxl2 17
#define pii pair<int,int>
#define fi first
#define se second
#define inf INT_MAX/2-1

using namespace std;

struct yes
{
  pii cap;
  int vmax;
};

int v[maxn+5], sp[maxn+5];
yes dp[maxn+5][maxl2+5]; ///dp[i][j] = rasp din [i,i+2^j-1]
int ans;

int getl2 ( int n, int pin )
{
  int l2 = log(n) / log(2);
  return l2 + ((1<<l2) < n && pin);
}

int getsp ( int a, int b )
{
  return sp[b+1] - sp[a];
}

int main ()
{
  ifstream fin ( "sequencequery.in" );
  ofstream fout ( "sequencequery.out" );

  int n, m; fin >> n >> m;

  int i, j, x, y, p, cur, ls, rs;
  for ( i = 0; i < n; i++ ) fin >> v[i], sp[i+1] = sp[i] + v[i];
  int en = getl2 ( n, 1 );
  for ( i = 0; i < n; i++ ) dp[i][0] = { {i,i}, v[i] };
  for ( i = 1; i <= en; i++ )
    for ( j = 0; j < n - (1<<i) + 1; j++ )
    {
      ls = j; rs = j+(1<<(i-1));

      if ( dp[ls][i-1].vmax > dp[rs][i-1].vmax )
        dp[j][i] = dp[ls][i-1];
      else dp[j][i] = dp[rs][i-1];
      if ( dp[ls][i-1].cap.se + 1 == dp[rs][i-1].cap.fi && dp[j][i].vmax < dp[ls][i-1].vmax + dp[rs][i-1].vmax )
        dp[j][i] = { {dp[ls][i-1].cap.fi,dp[rs][i-1].cap.se}, dp[ls][i-1].vmax + dp[rs][i-1].vmax };
    }

  pii iok;
  while (m--)
  {
    fin >> x >> y; cur = 0; ans = -inf;
    if ( x > y ) swap ( x, y );
    x--; y--; iok = {-1,-1};
    while ( x <= y )
    {
      p = getl2 ( y-x+1, 0 );
      cur += dp[x][p].vmax;
      if ( iok.se != -1 && cur + getsp (iok.se+1, dp[x][p].cap.fi-1) > ans )
      {
        ans = cur + getsp ( iok.se+1, dp[x][p].cap.fi-1 );
        iok.se = dp[x][p].cap.se;
      }
      if ( cur == dp[x][p].vmax && cur > ans )
      {
        ans = cur;
        iok = dp[x][p].cap;
      }
      cur = max(cur,0);
      x = dp[x][p].cap.se + 1;
    }
    fout << ans << '\n';
  }

  fin.close ();
  fout.close ();

  return 0;
}