#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 MAXN = 100005;
int A, B, S, rez;
int v[MAXN];

struct node{
    int L , R, best, sum;
};

node a[525000];

class ARBInt{
public:
    void update(int node, int st, int dr)
    {
        if(st == dr)
        {
            a[node].L=a[node].R=a[node].best=a[node].sum=v[st];
            return;
        }
        int mij = (st+dr) / 2 ;
        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;
        }
        int mij = (st+dr) / 2;
        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;
}