#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <ctime>
#include <utility>

using namespace std;

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

const int oo = (1LL<<64)-1;
const int MAXN = 100005;
int A, B, S, rez;
int v[MAXN];

struct node{
    int L , R, best, sum;
    void make_node(int a)
    {
        L = a;
        R = a;
        best = a;
        sum = a;
    }
};

    node a[525000];
class ARBInt{
public:
    void update(int node, int st, int dr)
    {
        if(st == dr)
        {
            a[node].make_node(v[st]);
            return;
        }
        else{
            int mij = (st+dr) >> 1;
            update(2*node, st, mij);
            update(2*node+1, mij+1, dr);
            a[node].L = max(a[2*node].L, a[2*node].sum + a[2*node+1].L);
            a[node].R = min(a[2*node+1].R, a[2*node+1].sum + a[2*node].R);
            a[node].best = max(max(a[2*node].best, a[2*node+1].best), a[2*node].R + a[2*node+1].L);
            a[node].sum = a[2*node].sum + a[2*node + 1].sum;
        }
    }
    void query(int node, int st, int dr)
    {
        if( A <= st && dr <= B )
        {
            if( S < 0 )
                S = 0;
            rez = max(rez, max(a[node].best, a[node].L + S));
            S = max(a[node].sum + S, a[node].R);
            return;
        }
        else {
            int mij = (st+dr) >> 1;
            if(A <= mij)
                query(2*node,st,mij);
            if(mij+1 <= B)
                query(2*node+1,mij+1,dr);
        }
    }
};

int main()
{
    ARBInt aint;
    int n, Q;
    cin >> n >> Q;
    for(int i = 1 ; i <= n ; ++ i)
        cin >> v[i];

    aint.update(1, 1, n);
    for(int i = 1 ; i <= Q; ++ i)
    {
        cin >> A >> B;
        S=0LL;
        rez=-10000000001LL;
        aint.query(1, 1, n);
        cout << rez << "\n";
    }
    return 0;
}