#include <bits/stdc++.h>

#define MAX_N 1000000

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[poz * 2].st, arb[poz * 2].sum + arb[poz * 2 + 1].st);
    arb[i].dr = max(arb[poz * 2 + 1].dr, arb[poz * 2 + 1].sum + arb[poz * 2].dr);
    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].rez),
                     arb[poz * 2 + 1].rez);

  //  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);
    }
}

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

    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);

    aint left = getRez(poz * 2, st, mid, a, mid);
    aint right = getRez(poz * 2 + 1, mid + 1, dr, mid + 1, b);

    aint cr;
    cr.st = max(left.st, left.sum + right.st);
    cr.dr = max(right.dr, right.sum + left.dr);
    cr.rez = max(max(max(cr.st, cr.dr), left.dr + max(right.st, 0LL)), max(left.dr, 0LL) + right.st);
    cr.rez = max(cr.rez, left.rez);
    cr.rez = max(cr.rez, right.rez);

    return cr;
}

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).rez);

        m --;
    }

    fclose(f);
    fclose(g);
}

int main()
{
    readFile();

    ansQues();

    return 0;
}