#include <fstream>

using namespace std;

struct Node
{
    long long sum;
    long long vmax;
    long long lmax;
    long long rmax;
};

long long sum, result;
int qleft, qright;
int pos, val;
Node tree[400002];

inline long long max3(long long a, long long b, long long c)
{
    if (a > b)
    {
        if (a > c)
            return a;
        return c;
    }
    if (b > c)
        return b;
    return c;
}

inline long long max2(long long a, long long b)
{
    if (a > b)
        return a;
    return b;
}

inline long long llmax(long long a, long long b)
{
    if (a > b)
        return a;
    return b;
}

void update(int i, int left, int right)
{
    if (pos < left || right < pos)
        return;
    if (left == right)
    {
        if (left == pos)
            tree[i].sum = tree[i].vmax = tree[i].lmax = tree[i].rmax = val;
        return;
    }
    int mid = (left+right)/2;
    update(2*i, left, mid);
    update(2*i+1, mid+1, right);
    tree[i].sum = tree[2*i].sum + tree[2*i+1].sum;
    tree[i].vmax = max3(tree[2*i].vmax, tree[2*i+1].vmax, tree[2*i].rmax + tree[2*i+1].lmax);
    tree[i].lmax = max2(tree[2*i].lmax, tree[2*i].sum + tree[2*i+1].lmax);
    tree[i].rmax = max2(tree[2*i+1].rmax, tree[2*i+1].sum + tree[2*i].rmax);
}

void query(int i, int left, int right)
{
    if (qright < left || qleft > right)
        return;
    if (qleft <= left && right <= qright)
    {
        sum = llmax(sum, 0);
        result = llmax(result, llmax(sum + 1LL * tree[i].lmax, tree[i].vmax));
        sum = llmax(sum + 1LL * tree[i].sum, tree[i].rmax);
        return;
    }
    if (left == right)
        return;
    int mid = (left+right)/2;
    query(2*i, left, mid);
    query(2*i+1, mid+1, right);
}

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

    int n, m;
    in >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        in >> val;
        pos = i;
        update(1, 1, n);
    }

    while (m--)
    {
        in >> qleft >> qright;
        sum = 0;
        result = -0x3f3f3f3f;
        query(1, 1, n);
        out << result << '\n';
    }

    return 0;
}