#include <iostream>
#include <fstream>

using namespace std;
using ll = long long;
const int NMAX = 1e5;
const ll INF = 1e8;

struct seg_tree {
      struct vertex {
            ll max_prefix, max_sufix;
            ll sum, ssm;
      } value[1 + 4 * NMAX];

      void merge_node ( int node, int left, int right ) {
          value[node].max_prefix = max ( value[node * 2].max_prefix, value[node * 2].sum + value[node * 2 + 1].max_prefix );
          value[node].max_sufix = max ( value[node * 2 + 1].max_sufix, value[node * 2 + 1].sum + value[node * 2].max_sufix );
          value[node].sum = value[node * 2].sum + value[node * 2 + 1].sum;
          value[node].ssm = max ( value[node * 2].ssm, value[node * 2 + 1].ssm );
          value[node].ssm = max ( value[node].ssm, value[node * 2].max_sufix + value[node * 2 + 1].max_prefix );
      }
      void update ( int node, int left, int right, int pos, int x ) {
          if ( left == right )
            value[node] = { x, x, x, x };
          else {
            int mid = left + ( right - left ) / 2;
            if ( pos <= mid )
              update ( node * 2, left, mid, pos, x );
            else
              update ( node * 2 + 1, mid + 1, right, pos, x );
            merge_node ( node, left, right );
          }
      }

      vertex query ( int node, int left, int right, int x, int y ) {
         if ( x <= left && right <= y )
           return value[node];
         int mid = left + ( right - left ) / 2;

         vertex first_node =  { -INF, -INF, 0, -INF };
         vertex second_node = { -INF, -INF, 0, -INF };
         if ( x <= mid )
           first_node = query ( node * 2, left, mid, x, y );
         if ( mid + 1 <= y )
           second_node = query ( node * 2 + 1, mid + 1, right, x, y );

         vertex new_node;
         new_node.sum = first_node.sum + second_node.sum;
         new_node.max_prefix = max ( first_node.max_prefix, first_node.sum + second_node.max_prefix );
         new_node.max_sufix = max ( second_node.max_sufix, second_node.max_sufix + first_node.max_sufix );
         new_node.ssm = max ( first_node.ssm, second_node.ssm );
         new_node.ssm = max ( new_node.ssm, first_node.max_sufix + second_node.max_prefix );

         return new_node;
      }
} aint;


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

int main()
{
   int n, q; fin >> n >> q;
   for ( int i = 1; i <= n; i ++ ) {
      int x; fin >> x;
      aint.update ( 1, 1, n, i, x );
   }
   for ( int i = 1; i <= q; i ++ ) {
      int x, y; fin >> x >> y;
      fout << aint.query ( 1, 1, n, x, y ).ssm << "\n";
   }
    return 0;
}