#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
struct qry{int l, r, idx;};
#define REP(i, a, b) for(int i = a; i < b; i++)
#define lb(v,x) (lower_bound(v,v+N,x)-v)
#define BSIZE 400
bool comp(qry a, qry b) {
if(a.l/BSIZE==b.l/BSIZE) return a.r<b.r;
return a.l<b.l;
}
int vec[121010];
#define MAXN 131072
int s[2*MAXN], e[2*MAXN], val[2*MAXN];
void init(int st, int en) {
s[1]=st; e[1]=en;
REP(i,1,131072) if(s[i]!=e[i]) {
//printf("%lld %lld %lld\n", i, s[i], e[i]);
int mid = (s[i] + e[i]) >> 1;
s[i<<1]=s[i];
e[i<<1]=mid;
s[i<<1|1]=mid+1,
e[i<<1|1]=e[i];
}
}
void update(int x, int u) {
int i = x + 131072;
val[i] += u;
while(i) {
i /= 2;
if(i) val[i] = max(val[i<<1],val[i<<1|1]);
}
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int N, Q, l=1,r=0; cin >> N >> Q;
ll ans[Q]; int arr[N+1], v[N+1];
init(0,131071);
REP(i,1,N+1) {cin>>arr[i]; vec[i-1]=arr[i];}
sort(vec,vec+N);
REP(i,1,N+1) v[i]=lb(vec,arr[i]);
qry query[Q];
REP(i,0,Q) {cin>>query[i].l>>query[i].r; query[i].idx=i;}
sort(query,query+Q,comp);
REP(i,0,Q) {
while(l>query[i].l) {l--;update(v[l],vec[v[l]]);}
while(l<query[i].l) {update(v[l],-vec[v[l]]);l++;}
while(r>query[i].r) {update(v[r],-vec[v[r]]);r--;}
while(r<query[i].r) {r++;update(v[r],vec[v[r]]);}
ans[query[i].idx]=val[1];
}
REP(i,0,Q) cout<<ans[i]<<"\n";
}
