IOI國曆史研究的第一人——JOI教授，最近獲得了一份被認為是古代IOI國的住民寫下的日記。JOI教授為了通過這份日記來研究古代IOI國的生活，開始着手調查日記中記載的事件。
日記中記錄了連續N天發生的時間，大約每天發生一件。
事件有種類之分。第i天(1<=i<=N)發生的事件的種類用一個整數Xi表示，Xi越大，事件的規模就越大。
JOI教授決定用如下的方法分析這些日記：
1. 選擇日記中連續的一些天作為分析的時間段
2. 事件種類t的重要度為t*(這段時間内重要度為t的事件數)
3. 計算出所有事件種類的重要度，輸出其中的最大值 現在你被要求制作一個幫助教授分析的程式，每次給出分析的區間，你需要輸出重要度的最大值。
這道題用莫隊添加很容易，但是删除很難，是以我們就用一個叫復原莫隊的東西。
我們定義l為目前詢問的左端點所在的塊的下一個塊的左端點，r為目前詢問的左端點所在的塊的右端點（一開始），由于排序之後，如果詢問的左端點所在的塊相同，那麼它們的詢問的右端點就會遞增。
那麼我們r就可以單調遞增，記錄答案為s2，l就向左改變到詢問的左端點，記錄最終答案為s1，然後l就向右移動回原來的位置，消除l向左的影響，s1=s2。那這道題就解決了。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
inline long long Max(long long a,long long b){return a>b?a:b;}
struct node
{
int l,r,id;
long long s;
node(){l=s=;}
}q[100010],b[];
int n,m,cnt;
int a[],belong[],ex[];
long long s1,s2,sum[],num[];
void fk()
{
cnt=sqrt(n);
for(int i=;i<=n;i++)belong[i]=(i-)/cnt+;
}
bool cmp1(node a,node b)
{
if(belong[a.l]==belong[b.l])
{
if(a.r>b.r)return false;
if(a.r<b.r)return true;
return ;
}
if(belong[a.l]>belong[b.l])return false;
if(belong[a.l]<belong[b.l])return true;
}
bool cmp2(node a,node b)
{
if(a.id>b.id)return false;
if(a.id<b.id)return true;
return ;
}
bool cmp3(node a,node b)
{
if(a.s>b.s)return false;
if(a.s<b.s)return true;
return ;
}
void add(int x)
{
sum[x]+=ex[x];
s1=Max(s1,sum[x]);
}
int main()
{
int ss=;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",&b[i].s),b[i].id=i;
sort(b+,b+n+,cmp3);
for(int i=;i<=n;i++)
{
if(b[i].s!=b[i-].s)ss++;
a[b[i].id]=ss;
ex[ss]=b[i].s;
}
for(int i=;i<=m;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;
}
fk();
sort(q+,q+m+,cmp1);
int l,r;
for(int i=;i<=m;i++)
{
if(belong[q[i].l]!=belong[q[i-1].l])
{
memset(sum,,sizeof(sum));
s1=s2=;
l=belong[q[i].l]*cnt+;r=l-;
}
if(belong[q[i].l]==belong[q[i].r])
{
long long ans=;
for(int j=q[i].l;j<=q[i].r;j++)
{
num[a[j]]+=ex[a[j]];ans=Max(ans,num[a[j]]);
}
q[i].s=ans;
for(int j=q[i].l;j<=q[i].r;j++)num[a[j]]-=ex[a[j]];
}
else
{
for(int j=r+;j<=q[i].r;j++)add(a[j]);
s2=s1;
for(int j=l-;j>=q[i].l;j--)add(a[j]);
q[i].s=s1;
for(int j=q[i].l;j<=l-;j++)sum[a[j]]-=ex[a[j]];
s1=s2;
r=q[i].r;
}
}
sort(q+,q+m+,cmp2);
for(int i=;i<=m;i++)printf("%lld\n",q[i].s);
return ;
}