#include <bits/stdc++.h>

using namespace std;

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

int n,m,in,sf,x,s;
int sums[400001],sumd[400001],sum[400001],sumsd[400001];


long long M(long long x, long long y){
    if(x>y)
        return x;
    else
        return y;
}

void updt(int nod, int st, int dr, int poz, int val){
    if(st==dr){
        sum[nod]=sumd[nod]=sums[nod]=sumsd[nod]=val;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)updt(nod*2,st,mij,poz,val);
    else updt(nod*2+1,mij+1,dr,poz,val);
    sums[nod]=M(sums[nod*2],sum[nod*2]+sums[nod*2+1]);
    sumd[nod]=M(sumd[nod*2+1],sum[nod*2+1]+sumd[nod*2]);
    sumsd[nod]=M(M(sumsd[nod*2],sumsd[nod*2+1]),sumd[nod*2]+sums[nod*2+1]);
    sum[nod]=sum[nod*2]+sum[nod*2+1];
}

void qry(int nod, int st, int dr){
    if(in<=st && dr<=sf){
        s=s+sumsd[nod];
        return;
    }
    int mij=(st+dr)/2;
    if(in<=mij)qry(nod*2,st,mij);
    if(mij<sf)qry(nod*2+1,mij+1,dr);
}

void build(int nod, int st, int dr){
    if(st==dr){
        sums[nod]=sumd[nod]=sumsd[nod];
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}

int main(){
    f>>n>>m;

    build(1,1,n);

    for(int i=1; i<=n; ++i){
        f>>x;
        updt(1,1,n,i,x);
    }
    for(int i=1; i<=m; ++i){
        f>>in>>sf;
        s=0;
        qry(1,1,n);
        g<<s<<'\n';
        g<<'\n';
    }
    return 0;
}