#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int imp[100010];
typedef long long ll;
ll ans[100010];
int in;
int data[100010];
int bck;
struct qr{int ind,l,r; bool operator<(const qr& other) const { return l/bck==other.l/bck?r<other.r:l<other.l; }; } query[100010];
int n,q;
ll tree[262144];
int main()
{
scanf("%d%d",&n,&q); int i; for(i=1;i<=n;++i) scanf("%d",data+i),imp[i]=data[i];
bck=n/sqrt(q);
sort(imp,imp+n);in=unique(imp,imp+n)-imp;
int a,b;
for(i=0;i<q;++i) scanf("%d%d",&a,&b),query[i].ind=i,query[i].l=a,query[i].r=b;
sort(query,query+q);
int l=query[0].l, r=query[0].r;
int tmp,ind;
for(i=l;i<=r;++i) {
tmp=data[i];
ind=lower_bound(imp,imp+in,tmp)-imp;
ind+=131072;
tree[ind]+=tmp;
ind/=2;
while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
}
ans[query[0].ind]=tree[1];
int ql,qr;
for(i=1;i<q;++i){
ql=query[i].l; qr=query[i].r;
while(ql<=l-1) {
tmp=data[--l];
ind=lower_bound(imp,imp+in,tmp)-imp;
ind+=131072;
tree[ind]+=tmp;
ind/=2;
while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
}
while(r+1<=qr) {
tmp=data[++r];
ind=lower_bound(imp,imp+in,tmp)-imp;
ind+=131072;
tree[ind]+=tmp;
ind/=2;
while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
}
while(l<ql) {
tmp=data[l++];
ind=lower_bound(imp,imp+in,tmp)-imp;
ind+=131072;
tree[ind]-=tmp;
ind/=2;
while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
}
while(qr<r) {
tmp=data[r--];
ind=lower_bound(imp,imp+in,tmp)-imp;
ind+=131072;
tree[ind]-=tmp;
ind/=2;
while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
}
ans[query[i].ind]=tree[1];
}
for(i=0;i<q;++i) printf("%lld\n",ans[i]);
return 0;
}
