#include <fstream>

using namespace std;

ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");

struct TreeNode
{
    long long sum, prefsmax, sufsmax, secsmax;
}aint[2 * 100001];

int n, a[100001];
int m;

TreeNode UpdateNode(TreeNode left, TreeNode right)
{
    TreeNode NodeCur;
    NodeCur.sum = left.sum + right.sum;
    NodeCur.prefsmax = max(left.prefsmax, left.sum + right.prefsmax);
    NodeCur.sufsmax = max(right.sufsmax, right.sum + left.sufsmax);
    NodeCur.secsmax = max(left.sufsmax + right.prefsmax, max(left.secsmax, right.secsmax));
    return NodeCur;
}

void Build(int node, int left, int right)
{
    if(left == right)
    {
        aint[node].sum = a[left];
        aint[node].prefsmax = a[left];
        aint[node].sufsmax = a[left];
        aint[node].secsmax = a[left];
    }
    else
    {
        int mid = (left + right) / 2;
        Build(node * 2, left, mid);
        Build(node * 2 + 1, mid + 1, right);
        aint[node] = UpdateNode(aint[node * 2], aint[node * 2 + 1]);
    }
}

TreeNode Query(int node, int left, int right, int Qleft, int Qright)
{
    if(left >= Qleft && right <= Qright)
        return aint[node];

    int mid = (left + right) / 2;
    if(mid >= Qright)
        return Query(node * 2, left, mid, Qleft, Qright);
    if(mid + 1 <= Qleft)
        return Query(node * 2 + 1, mid + 1, right, Qleft, Qright);

    TreeNode leftvalue = Query(node * 2, left, mid, Qleft, Qright);
    TreeNode rightvalue = Query(node * 2 + 1, mid + 1, right, Qleft, Qright);
    return UpdateNode(leftvalue, rightvalue);
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    Build(1, 1, n);

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        /// Query
        cout << Query(1, 1, n, x, y).secsmax << '\n';
    }

    return 0;
}