#include <fstream>
#include <cmath>
#include <limits>
using namespace std;

struct node
{
    int leftPos;
    int rightPos;
    long long sum;
    node()
    {
        leftPos = 0;
        rightPos = 0;
        sum = numeric_limits<long long>::min();
    }
};

long long getSum(int left, int right, long long pSums[])
{
    if (right == 0 || left - 1 < 0)
        return numeric_limits<long long>::min();

    return pSums[right] - pSums[left - 1];
}

void update(int index, int pos, int val, int left, int right, node tree[], long long pSums[])
{
    if (left == right)
    {
        tree[index].leftPos = tree[index].rightPos = left;
        tree[index].sum = val;
    }
    else
    {
        int mid = (left + right) >> 1;
        if (pos <= mid)
            update(index * 2, pos, val, left, mid, tree, pSums);
        else
            update(index * 2 + 1, pos, val, mid + 1, right, tree, pSums);

        int left = index << 1;
        int right = (index << 1) + 1;

        tree[index] = tree[left];
        if (tree[right].sum >= tree[index].sum)
            tree[index] = tree[right];

        if (getSum(tree[left].leftPos, tree[right].rightPos, pSums) > tree[index].sum)
        {
            tree[index].leftPos = tree[left].leftPos;
            tree[index].rightPos = tree[right].rightPos;
            tree[index].sum = getSum(tree[index].leftPos, tree[index].rightPos, pSums);
        }
    }
}

node query(int index, int left, int right, int cLeft, int cRight, node tree[], long long pSums[])
{
    if (cLeft >= left && cRight <= right)
        return tree[index];

    int middle = (cLeft + cRight) >> 1;
    node leftTree, rightTree;
    if (middle >= left)
        leftTree = query(index * 2, left, right, cLeft, middle, tree, pSums);
    if (middle + 1 <= right)
        rightTree = query(index * 2 + 1, left, right, middle + 1, cRight, tree, pSums);

    node result = leftTree;
    if (rightTree.sum > result.sum)
        result = rightTree;
    if (getSum(leftTree.leftPos, rightTree.rightPos, pSums) > result.sum)
    {
        result.leftPos = leftTree.leftPos;
        result.rightPos = rightTree.rightPos;
        result.sum = getSum(leftTree.leftPos, rightTree.rightPos, pSums);
    }

    return result;
}

int main()
{
    int x, y, N, M, i;
    ifstream f("sequencequery.in");
    f >> N >> M;
    int length = (1 << ((int)log2(N) + 2));
    node tree[length];
    long long pSums[N + 1];

    pSums[0] = 0;
    for (i = 1; i <= N; i++)
    {
        f >> x;
        pSums[i] = pSums[i - 1] + x;
        update(1, i, x, 1, N, tree, pSums);
    }

    ofstream g("sequencequery.out");
    for (i = 1; i <= M; i++)
    {
        f >> x >> y;
        g << query(1, x, y, 1, N, tree, pSums).sum << '\n';
    }
    f.close();
    g.close();
    return 0;
}