#include "bits/stdc++.h"
using namespace std;
const int N=1e5+5,Q=1e5+5;
const int S = 600;
struct Query{
int l,r,p,bk;
};
Query qr[Q];
int n,q,x[N];
struct node{
int s,e,m; long long val;
node *l, *r;
node(int _s, int _e){
s=_s; e=_e;
m=(s+e)>>1;
val = 0;
}
void create(){
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void upd(int p, int v){
if(s==e) val += (long long) v;
else{
if(l==NULL) create();
if(p<=m) l->upd(p,v);
else r->upd(p,v);
val = max(l->val,r->val);
}
}
long long qry(){
return val;
}
} *root;
bool comp(Query A, Query B){
if(A.bk != B.bk) return A.bk < B.bk;
return A.bk % 2 ? A.r > B.r : A.r < B.r;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>n>>q;
for(int i=1; i<=n; i++) cin>>x[i];
for(int i=0; i<q; i++){
cin>>qr[i].l>>qr[i].r;
qr[i].p = i;
qr[i].bk = qr[i].l / S;
}
sort(qr,qr+q,comp);
root = new node(0,(int) 1e9+5);
int mo_left = 1, mo_right = 0;
long long ans[q];
for(int i=0; i<q; i++){
int left = qr[i].l, right = qr[i].r;
while(mo_right < right){
++mo_right;
int t = x[mo_right];
root->upd(t,t);
}
while(mo_left > left){
--mo_left;
int t = x[mo_left];
root->upd(t,t);
}
while(mo_right > right){
int t = x[mo_right];
root->upd(t,-t);
--mo_right;
}
while(mo_left < left){
int t = x[mo_left];
root->upd(t,-t);
++mo_left;
}
ans[qr[i].p] = root->qry();
//cout<<"HI"<<endl;
//cout<<qr[i].l<<' '<<qr[i].r<<' '<<ans[qr[i].p]<<endl;
}
for(int i=0; i<q; i++) cout<<ans[i]<<'\n';
}
