#include <fstream>
#define DIM 100002
#define INF 2e18

using namespace std;

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

int n, m, v[DIM], x, y;
long long sdr, smax;

struct arbint{
    long long st, dr, smax, stot;
}aint[4 * DIM];

void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod].st = v[st];
        aint[nod].dr = v[st];
        aint[nod].smax = v[st];
        aint[nod].stot = v[st];
        return;
    }

    int mid = (st + dr) / 2;

    build(nod<<1, st, mid);
    build(nod<<1|1, mid + 1, dr);

    aint[nod].stot = aint[nod<<1].stot + aint[nod<<1|1].stot;
    aint[nod].st = max(aint[nod<<1].st, aint[nod<<1].stot + aint[nod<<1|1].st);
    aint[nod].dr = max(aint[nod<<1|1].dr, aint[nod<<1|1].stot + aint[nod<<1].dr);
    aint[nod].smax = max(aint[nod<<1].dr + aint[nod<<1|1].st,max(aint[nod<<1].smax, aint[nod<<1|1].smax));
}

void query(int nod, int st, int dr, int a, int b){
    if(a <= st && b >= dr){
        smax = max(aint[nod].st + sdr, max(smax, aint[nod].smax));
        sdr = max(sdr + aint[nod].stot, aint[nod].dr);
        return;
    }

    int mid = (st + dr) / 2;

    if(a <= mid)
        query(nod<<1, st, mid, a, b);
    if(b > mid)
        query(nod<<1|1, mid + 1, dr, a, b);
}

int main()
{
    in>>n>>m;
    for(int i = 1; i <= n; ++ i)
        in>>v[i];
    build(1, 1, n);
    for(int i = 1; i <= m; ++ i){
        in>>x>>y;
        if(x > y)
            swap(x, y);
        sdr = -INF;
        smax = -INF;
        query(1, 1, n, x, y);
        out<<smax<<'\n';
    }
    return 0;
}