#include <bits/stdc++.h>

using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
const int N = 1e5+5;
struct a
{
    long long sum,best,left,right;
} tree[4*N];
void update(int node, int st, int dr, int poz, int val)
{
    if (st == dr)
        tree[node].best = tree[node].left = tree[node].right = tree[node].sum = val;
    else
    {
        int mj = (st+dr)/2;
        if (poz<=mj)
            update(2*node,st,mj,poz,val);
        else
            update(2*node+1,mj+1,dr,poz,val);

        tree[node].left = max(tree[2*node].sum+tree[2*node+1].left,tree[2*node].left);
        tree[node].right = max(tree[2*node+1].sum+tree[2*node].right,tree[2*node+1].right);
        tree[node].sum = tree[2*node].sum+tree[2*node+1].sum;
        tree[node].best = max(tree[2*node].right+tree[2*node+1].left,max(tree[2*node].best,tree[2*node+1].best));
    }
}
a query(int node, int st, int dr, int x, int y)
{
    if (x<=st && dr<=y)
        return tree[node];
    else
    {
        int mj = (st+dr)/2;
        if (x<=mj && y<=mj)
            return query(2*node,st,mj,x,y);
        if (x>mj && y>mj)
            return query(2*node+1,mj+1,dr,x,y);
        if (x<=mj && y>mj)
        {
            a L = query(2*node,st,mj,x,y);
            a R = query(2*node+1,mj+1,dr,x,y);
            a now;
            now.left = max(L.sum+R.left,L.left);
            now.right = max(R.sum+L.right,R.right);
            now.sum = L.sum+R.sum;
            now.best = max(L.right+R.left,max(L.best,R.best));
            return now;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    in >> n >> m;
    for (int i = 1; i<=n; i++)
    {
        long long x;
        in >> x;
        update(1,1,n,i,x);
    }
    for (int i = 1; i<=m; i++)
    {
        int x,y;
        in >> x >> y;
        out << query(1,1,n,x,y).best << "\n";
    }
}