#include<fstream>
using namespace std;
int main() {
    int s,n,i,v[100001],max,l1,l2,lr,k,a,b,j;
    ifstream in("sequencequery.in");
    ofstream out("sequencequery.out");
    in>>n>>k;
    for(i=1; i<=n; i++)
        in>>v[i];
    for(i=1; i<=k; i++) {
        in>>a>>b;
        s=0;
        max=-1000000000;
        for(j=a; j<=b; j++) {
            s+=v[j];
            if(v[j]>max) {
                max=v[j];
                lr=j;
                l2=j;
            }
            if(s>max) {
                max=s;
                lr=l1;
                l2=j;
            }
            if(s<0) {
                s=0;
                l1=j+1;
            }
        }
        out<<max<<"\n";
    }
    return 0;
}