/*huypheu
5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
int le[100007],ri[100007];
int ans[100007];
map <int,int> mymap;
int it[400007];
int blo;
int a[100007],b[100007];
int v[100007];
vector <int> ve;
void update(int node,int l,int r,int x,int p)
{
// if(node==1) cout << x << " " << p << endl;
// cout << node << " " << l << " " << r << endl;
if(l>r || x<l || r<x) return ;
if(l==r)
{
it[node]+=p;
// cout << node << " " << p << endl;
return ;
}
int mid=(l+r)/2;
update(node*2,l,mid,x,p);
update(node*2+1,mid+1,r,x,p);
it[node]=max(it[node*2],it[node*2+1]);
return ;
}
int get(int node,int l,int r,int x,int y)
{
if(l>r || y<l || r<x) return 0;
if(x<=l && r<=y)
{
return it[node];
}
int mid=(l+r)/2;
return max(get(node*2,l,mid,x,y),get(node*2+1,mid+1,r,x,y));
}
bool dcp1(int x,int y)
{
return (a[x]<a[y]);
}
bool dcp(int x,int y)
{
if((le[x]/blo)!=(le[y]/blo)) return ((le[x]/blo)<(le[y]/blo));
else if(ri[x]!=ri[y]) return (ri[x]<ri[y]); else return (le[x]<le[y]);
}
signed main()
{
// ios_base::sync_with_stdio(false);
// cin.tie(0);
int n,q;
scanf("%lld %lld",&n,&q);
// cin >> n >> q;
blo=(int)sqrt(n);
// cout << blo << endl;
int m=0;
set <int> se;
for(int i=1;i<=n;i++)
{
// cin >> a[i];
scanf("%lld",&a[i]);
// cout << a[i] << " ";
se.insert(a[i]);
v[i]=i;
// m=max(m,b[i]);
}
sort(v+1,v+n+1,dcp1);
for(int i=1;i<=n;i++)
{
if(i==1 || a[v[i]]!=a[v[i-1]]) m++;
b[v[i]]=m;
}
// for(int i=1;i<=n;i++) cout << b[i] << " " << a[i] << endl;
// cout << endl;
// for(int i=1;i<=n;i++) cout << b[i] << " ";
// cout << endl;
// cout << endl;
for(int i=1;i<=q;i++)
{
scanf("%lld %lld",&le[i],&ri[i]);
ve.push_back(i);
}
sort(ve.begin(),ve.end(),dcp);
int l=le[ve[0]],r=le[ve[0]]-1;
for(int i=0;i<ve.size();i++)
{
// cout << le[ve[i]] << " " << ri[ve[i]] << endl;
while(l>le[ve[i]])
{
l--;
update(1,1,m,b[l],a[l]);
}
while(l<le[ve[i]])
{
l++;
update(1,1,m,b[l-1],-a[l-1]);
}
while(r<ri[ve[i]])
{
r++;
update(1,1,m,b[r],a[r]);
}
while(r>ri[ve[i]])
{
r--;
update(1,1,m,b[r+1],-a[r+1]);
}
ans[ve[i]]=get(1,1,m,1,m);
// cout << it[1] << endl;
}
for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
return 0;
}
