#include <iostream>
#include <fstream>
#define nl '\n'

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

const int NMAX = 1e5+5;

int n;
long long int suf, maxi;
struct info
{
    long long int sum, sumaMax, sufMax, prefMax;
} aint[4*NMAX];

void build(int node, int st, int dr)
{
    if (st == dr)
    {
        int x;
        fin >> x;
        aint[node] = {x, x, x, x};
    }
    else
    {
        int mid = (st+dr)/2;
        build(2*node, st, mid);
        build(2*node+1, mid+1, dr);
        aint[node].sum = aint[2*node].sum + aint[2*node+1].sum;
        aint[node].prefMax = max(aint[2*node].prefMax, aint[2*node].sum+aint[2*node+1].prefMax);
        aint[node].sufMax = max(aint[2*node+1].sufMax, aint[2*node+1].sum+aint[2*node].sufMax);
        aint[node].sumaMax = max(aint[2*node].sumaMax, aint[2*node+1].sumaMax);
        aint[node].sumaMax = max(aint[node].sumaMax, aint[2*node].sufMax+aint[2*node+1].prefMax);
    }
    return;
}

void query(int node, int st, int dr, int a, int b)
{
    if (a <= st && dr <= b)
    {
        maxi = max(maxi, aint[node].sumaMax);
        maxi = max(maxi, suf+aint[node].prefMax);
        suf = max(suf+aint[node].sum, aint[node].sufMax);
        return;
    }
    int mid = (st+dr)/2;
    if (a <= mid)
        query(2*node, st, mid, a, b);
    if (mid+1 <= b)
        query(2*node+1, mid+1, dr, a, b);
    return;
}

int main()
{
    int m;
    fin >> n >> m;
    build(1, 1, n);
    while (m--)
    {
        int a, b;
        fin >> a >> b;
        maxi = suf = -1e18;
        query(1, 1, n, a, b);
        fout << maxi << nl;
    }
    return 0;
}