#include <iostream>
#include <fstream>
#define DEBUG 0

using namespace std;

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

const int INF = 100001;
int v[100001];

struct branch
{
    int s = -INF, l = -INF, r = -INF, m = -INF;
} tree[400400];

void build(int node, int left, int right)
{
    if(left == right)
    {
        tree[node].s = v[left];
        tree[node].m = v[left];
        tree[node].l = v[left];
        tree[node].r = v[left];
        return;
    }

    int mid = (left+right) >> 1;
    int ls = node << 1, rs = ls | 1;

    if(DEBUG)
    {
        cout << node << ' ' << ls << ' ' << rs << '\n';
    }

    build(ls, left, mid);
    build(rs, mid+1, right);

    tree[node].s = tree[ls].s + tree[rs].s;
    tree[node].l = max(tree[ls].l, tree[ls].s + tree[rs].l);
    tree[node].r = max(tree[rs].r, tree[rs].s + tree[ls].r);
    tree[node].m = max(tree[ls].m, max(tree[rs].m, tree[ls].r + tree[rs].l));
}

void query(int ql, int qr, int node, int left, int right, int &rez, int &best)
{
    if(left > qr || right < ql)
        return;

    if(ql <= left && right <= qr)
    {
        rez = max(rez, max(tree[node].m, best + tree[node].l));
        best = max(best + tree[node].s, tree[node].r);\
        return;
    }

    int mid = (left+right) >> 1;
    int ls = node<<1, rs = ls | 1;

    if(DEBUG)
        cout << "node:" << node << "    left and right:" << left << ' ' << right << "    ql and qr:" << ql << ' ' << qr << "   rez and best:" << rez << ' ' << best << '\n';

    query(ql, qr, ls, left, mid, rez, best);
    query(ql, qr, rs, mid+1, right, rez, best);
}

int main()
{
    int n, m;
    in >> n >> m;

    for(int i = 1; i <= n; i++)
        in >> v[i];

    build(1, 1, n);

    if(DEBUG)
    {
        cout << '\n' << '\n';
        for(int i = 1; i <= 15; i++)
            cout << "node:" << i << " s:" << tree[i].s << " m:" << tree[i].m << " l:" << tree[i].l << " r:" << tree[i].r << '\n';
        cout << '\n' << '\n';
    }

    while(m)
    {
        int x,y;
        int rez = -INF, best = -INF;
        in >> x >> y;
        query(x, y, 1, 1, n, rez, best);
        out << rez << '\n';
        m--;
    }

    return 0;
}