#include <iostream>
#include <fstream>
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
#define N_MAX 200005
long long aint[N_MAX << 2], l[N_MAX << 2], r[N_MAX << 2], sum[N_MAX << 2];
int n, m;
void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        f >> aint[nod];
        sum[nod] = aint[nod];
        l[nod] = r[nod] = aint[nod];
        return;
    }

    int left = nod * 2;
    int right = nod * 2 + 1;
    int mid = (st + dr) / 2;

    build(left, st, mid);
    build(right, mid + 1, dr);

    l[nod] = max(l[left], sum[left] + l[right]);
    r[nod] = max(r[right], r[left] + sum[right]);
    aint[nod] = max(max(aint[left], aint[right]), r[left]+l[right]);
    sum[nod] = sum[left] + sum[right];
}

int pos, val;

int x,y;

long long rez, S;

void query(int nod, int st, int dr)
{
    if(x <= st && y >= dr)
    {
        rez = max(rez, max(S + l[nod], aint[nod]));
        S = max(S + sum[nod], r[nod]);
    }
    else
    {
        int left = nod * 2;
        int right = nod * 2 + 1;
        int mid = (st + dr) / 2;

        if(x <= mid) query(left, st, mid);
        if(y > mid) query(right, mid + 1, dr);
    }
}
int main()
{
    f >> n >> m;
    build(1, 1, n);
    int a, b;
    for(int i = 1; i <= m; i++)
    {
        f >> a >> b;
        S = rez = -(1LL<<30);

        x = a;
        y = b;

        query(1, 1, n);

        g << rez << "\n";
    }
    return 0;
}