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

/// INPUT / OUTPUT
const string problem = "sequencequery";
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");

/// STRUCTURES
struct tree_node
{
    int st, dr, max, suma;  
};

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

inline tree_node update_node(tree_node left, tree_node right)
{
    tree_node curr_node;
    curr_node.suma = left.suma + right.suma;
    curr_node.st = max(left.st, left.suma + right.st);
    curr_node.dr = max(right.dr, right.suma + left.dr);
    curr_node.max = max({left.dr + right.st, left.max, right.max});
    return curr_node;
}

inline void build(int node, int st, int dr)
{
    if(st == dr)
    {
        tree[node].st = arr[st];
        tree[node].dr = arr[st];
        tree[node].max = arr[st];
        tree[node].suma = 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 void query(int node, int st, int dr, int arbst, int arbdr)
{
    if(st > arbdr || dr < arbst)
        return;
    if(dr <= arbdr && st >= arbst)
    {
        last_node = update_node(last_node, tree[node]);
        ans = max(ans, last_node.max);
    }
    int mid = (st + dr) / 2;
    query(node*2, st, mid, arbst, arbdr);
    query(node*2+1, mid + 1, dr, arbst, arbdr);
}

/// READING THE INPUT
int main()
{
    fin >> n >> q;
    for(int i = 1; i <= n; ++ i)
    {
        fin >> arr[i];
    }
    build(1, 1, n);
    while(q--)
    {
        int a, b;
        fin >> a >> b;
        ans = INT_MIN;
        last_node.suma = 0;
        last_node.max = 0;
        last_node.st = 0;
        last_node.dr = 0;
        query(1, 1, n, a, b);
        fout << ans << '\n';
    }
}