#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("sequencequery.in");
ofstream fout("sequencequery.out");
int n, m ,x ,y, i, ok;
long long mm,sol;
long long a[600010],b[600010],c[600010],d[600010];

void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        fin>>b[nod];
        c[nod]=b[nod];
        a[nod]=b[nod];
        d[nod]=b[nod];
    }
    else
    {
        int mid=(st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        a[nod]=max(a[nod*2], a[nod*2+1]);
        a[nod]=max(b[nod*2]+c[nod*2+1], a[nod]);
        b[nod]=max(b[2*nod+1], b[2*nod]+d[2*nod+1]);
        c[nod]=max(c[2*nod], c[2*nod+1]+d[2*nod]);
        d[nod]=d[nod*2]+d[nod*2+1];
    }
}

void update(int nod, int st, int dr, int poz, int val)
{
    if(st==dr)
    {
        b[nod]=val;
        c[nod]=b[nod];
        a[nod]=b[nod];
        d[nod]=b[nod];
    }
    else
    {
        int mid=(st+dr)/2;
        if(poz<=mid)
            update(2*nod, st, mid, poz, val);
        if(poz>mid)
            update(2*nod+1, mid+1, dr, poz, val);
        a[nod]=max(a[nod*2], a[nod*2+1]);
        a[nod]=max(b[nod*2]+c[nod*2+1], a[nod]);
        b[nod]=max(b[2*nod+1], b[2*nod]+d[2*nod+1]);
        c[nod]=max(c[2*nod], c[2*nod+1]+d[2*nod]);
        d[nod]=d[nod*2]+d[nod*2+1];
    }
}

void vas(int nod, int st, int dr, int x, int y)
{
    if(x<=st&&y>=dr)
    {
        sol=max(sol, a[nod]);
        sol=max(sol, mm+c[nod]);
        if(b[nod]>d[nod]+mm)
            mm=b[nod];
        else
            mm=d[nod]+mm;
        sol=max(sol, mm);
    }
    else
    {
        int mid=(st+dr)/2;
        if(x<=mid)
            vas(2*nod, st, mid, x, y);
        if(mid+1<=y)
            vas(2*nod+1, mid+1, dr, x ,y);
    }
}

int main(){
    fin>>n>>m;
    build(1, 1, n);
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        sol=-1000000;
        mm=0;
        vas(1, 1, n, x, y);
        fout<<sol<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}