#include <bits/stdc++.h>
using namespace std;

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

/// STRUCTURES
struct tree_node {
  long long sum; // suma subsecventei
  long long pref_scmax; // prefixul de suma maxim
  long long suff_scmax; // sufixul de suma maxima
  long long scmax; // subsecventa de suma maxima
};

/// GLOBAL VARIABLES
const int NMAX = 1e5+5;
int n, q, ans;
int arr[NMAX];
vector<pair<int,int>>queries;
tree_node tree[4*NMAX];

tree_node update_node(tree_node left_node, tree_node right_node)
{
  tree_node current_node;

  current_node.sum =
      left_node.sum + right_node.sum;

  current_node.pref_scmax =
      std::max(left_node.pref_scmax,
               left_node.sum + right_node.pref_scmax);

  current_node.suff_scmax =
      std::max(right_node.suff_scmax,
               right_node.sum + left_node.suff_scmax);

  current_node.scmax =
      std::max(left_node.suff_scmax + right_node.pref_scmax,
               std::max(left_node.scmax, right_node.scmax));

  return current_node;
}

inline void build(int node, int st, int dr)
{
    if(st == dr)
    {
        tree[node].sum = arr[st];
        tree[node].pref_scmax = arr[st];
        tree[node].suff_scmax = arr[st];
        tree[node].scmax = arr[st];
    }
    else
    {
        int mid = (st + dr) / 2;
        build(node * 2, st, mid);
        build(node * 2 + 1, mid + 1, dr);
        tree[node] = update_node(tree[node*2], tree[node*2+1]);
    }
}

inline tree_node query(int node, int st, int dr, int arbst, int arbdr)
{
    if(arbdr >= dr && arbst <= st)
    {
        return tree[node];
    }
    else
    {
        int mid = (st + dr) / 2;
        if(arbdr <= mid)
            return query(node*2, st, mid, arbst, arbdr);
        if(mid + 1 <= arbst)
            return query(node*2+1, mid + 1, dr, arbst, arbdr);
        tree_node left_node = query(node*2, st, mid, arbst, arbdr);
        tree_node right_node = query(node*2+1, mid + 1, dr, arbst, arbdr);
        return update_node(left_node, right_node);
    }
}

/// READING THE INPUT
int main()
{
    fin >> n >> q;
    for(int i = 1; i <= n; ++ i)
    {
        fin >> arr[i];
    }
    build(1,1,n);
    for(int i = 1; i <= q; ++ i)
    {
        int x, y;
        fin >> x >> y;
        fout << query(1, 1, n, x, y).scmax << '\n';
    }
}