#include <bits/stdc++.h>

#define MAX_N 100000

using namespace std;

FILE *f, *g;

typedef long long lint;

struct aint
{
    lint st, dr, sum, rez;
};

aint arb[MAX_N * 4 + 1];

void upd(int poz, int st, int dr, int loc, int nr)
{
    int i = poz;
    if(st == dr)
    {
        arb[i].rez = arb[i].st = arb[i].dr = arb[i].sum = nr;

        return;
    }

    int mid = (st + dr) >> 1;

    if(st <= loc && loc <= mid)
        upd(poz * 2, st, mid, loc, nr);

    if(mid < loc && loc <= dr)
        upd(poz * 2 + 1, mid + 1, dr, loc, nr);


    arb[i].sum = arb[poz * 2].sum + arb[poz * 2 + 1].sum;
    arb[i].st = /*max(arb[i].sum, */max(arb[poz * 2].st, arb[poz * 2].sum + max(arb[poz * 2 + 1].st, 0LL))/*)*/;
    arb[i].dr = /*max(arb[i].sum, */max(arb[poz * 2 + 1].dr, arb[poz * 2 + 1].sum + max(arb[poz * 2].dr, 0LL))/*)*/;
    arb[i].rez = max(max(max(max(arb[i].st, arb[i].dr),
                     arb[poz * 2].dr + arb[poz * 2 + 1].st),
                     arb[poz * 2].dr),
                     arb[poz * 2 + 1].st);

  //  cout << st << " " << dr << " " << arb[i].st << " " << arb[i].dr << " " << arb[i].sum << " " << arb[i].rez << "\n";
}

int n, m;

void readFile()
{
    f = fopen("sequencequery.in", "r");

    fscanf(f, "%d%d", &n, &m);

    int i, nr;
    for(i = 1; i <= n; i ++)
    {
        fscanf(f, "%d", &nr);

        //cout << "BAGA " << i << " " << nr << "\n";
        upd(1, 1, n, i, nr);
    }
}

lint getDr(int poz, int st, int dr, int a, int b)
{
    //cout << "DR " << st << " " << dr << " " << a << " " << b << "\n";

    if(dr < st)
        return 0;

    if(st == a && dr == b /*|| (st == dr)*/)
        return arb[poz].dr;

    int mid = (st + dr) >> 1;

    if(a >= st && b <= mid)
        return getDr(poz * 2, st, mid, a, b);

    if(a > mid && b <= dr)
        return getDr(poz * 2 + 1, mid + 1, dr, a, b);

    return max(getDr(poz * 2, st, mid, a, mid) + arb[poz * 2 + 1].sum,
               getDr(poz * 2 + 1, mid + 1, dr, mid + 1, b));
}

lint getSt(int poz, int st, int dr, int a, int b)
{
    //cout << "ST " << st << " " << dr << " " << a << " " << b << "\n";

    if(dr < st)
        return 0;

    if(st == a && dr == b)
        return arb[poz].st;

    int mid = (st + dr) >> 1;

    if(a >= st && b <= mid)
        return getSt(poz * 2, st, mid, a, b);

    if(a > mid && b <= dr)
        return getSt(poz * 2 + 1, mid + 1, dr, a, b);

    return max(getSt(poz * 2 + 1, mid + 1, dr, a, b) + arb[poz * 2].sum,
               getSt(poz * 2, st, mid, a, b));
}

lint getRez(int poz, int st, int dr, int a, int b)
{
    if(st == a && dr == b)
        return arb[poz].rez;

    int mid = (st + dr) >> 1;

    if(a >= st && b <= mid)
        return getRez(poz * 2, st, mid, a, b);

    if(a > mid && b <= dr)
        return getRez(poz * 2 + 1, mid + 1, dr, a, b);

    lint reza = getDr(poz * 2, st, mid, a, mid);
    lint rezb = getSt(poz * 2 + 1, mid + 1, dr, mid + 1, b);

    return max(reza, max(rezb, reza + rezb));
}

void ansQues()
{
    g = fopen("sequencequery.out", "w");

    int st, dr;
    while(m > 0)
    {
        fscanf(f, "%d%d", &st, &dr);

        fprintf(g, "%lld\n", getRez(1, 1, n, st, dr));

        m --;
    }

    fclose(f);
    fclose(g);
}

int main()
{
    readFile();

    ansQues();

    return 0;
}