#include <iostream>
#include <algorithm>
#define lol long long

using namespace std;

FILE *fin = fopen("sequencequery.in", "r");
FILE *fout = fopen("sequencequery.out", "w");

int n, m;
lol v[100005];

struct node
{
    lol containing;
    lol fromLeft;
    lol fromRight;
    lol total;
};

node seg_tree[500005];

node &l(int pos)
{
    return seg_tree[pos * 2 + 1];
}

node &r(int pos)
{
    return seg_tree[pos * 2 + 2];
}

void update_up(int pos)
{
    seg_tree[pos].total = l(pos).total + r(pos).total;
    seg_tree[pos].fromLeft = max(l(pos).total + r(pos).fromLeft, l(pos).fromLeft);
    seg_tree[pos].fromRight = max(r(pos).total + l(pos).fromRight, r(pos).fromRight);
    seg_tree[pos].containing = max(l(pos).containing, r(pos).containing);
    seg_tree[pos].containing = max(seg_tree[pos].containing, r(pos).fromLeft + l(pos).fromRight);
    if (pos != 0)
        update_up((pos + 1) / 2 - 1);
}

void push(int pos, int val, int a, int low, int high)
{
    if (low == high)
    {
        seg_tree[pos].total += val;
        seg_tree[pos].fromLeft += val;
        seg_tree[pos].fromRight += val;
        seg_tree[pos].containing += val;
        update_up((pos + 1) / 2 - 1);
    }
    else
    {
        int mid = (low + high) / 2;
        if (a <= mid)
            push(pos * 2 + 1, val, a, low, mid);
        else
            push(pos * 2 + 2, val, a, mid + 1, high);
    }
}

node getInterval(int pos, lol a, lol b, int low, int high)
{
    if (low == high)
        return seg_tree[pos];
    if (a <= low && high <= b)
        return seg_tree[pos];
    int mid = (low + high) / 2;
    if (b <= mid)
        return getInterval(pos * 2 + 1, a, b, low, mid);
    if (a >= mid + 1)
        return getInterval(pos * 2 + 2, a, b, mid + 1, high);

    node left = getInterval(pos * 2 + 1, a, b, low, mid);
    node right = getInterval(pos * 2 + 2, a, b, mid + 1, high);
    node current;
    current.total = left.total + right.total;
    current.fromLeft = max(left.total + right.fromLeft, left.fromLeft);
    current.fromRight = max(right.total + left.fromRight, right.fromRight);
    current.containing = max(left.containing, right.containing);
    current.containing = max(current.containing, right.fromLeft + left.fromRight);
    return current;
}

int main()
{
    fscanf(fin, "%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        fscanf(fin, "%lld", &v[i]);
        push(0, v[i], i, 0, n - 1);
    }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        fscanf(fin, "%d %d", &a, &b);
        a--;
        b--;
        fprintf(fout, "%lld\n", getInterval(0, a, b, 0, n - 1).containing);
    }
}