#include<bits/stdc++.h> #define MAXN 100005 #define int long long usingnamespace std; inlineintread(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } int a[MAXN],b[MAXN],org[MAXN],pos[MAXN],n,m; structQuery{ int l,r; int id; }q[MAXN]; inlinebooloperator < (const Query &A,const Query &B){ return pos[A.l]==pos[B.l]?A.r<B.r:pos[A.l]<pos[B.l]; } inlinevoiddiscrete(){ for (registerint i=1;i<=n;++i) b[i]=a[i]; sort(b+1,b+1+n); int s=unique(b+1,b+1+n)-b-1; for (registerint i=1;i<=n;++i){ a[i]=lower_bound(b+1,b+1+s,a[i])-b; } } int Size,cnt[MAXN],Ans[MAXN]; inlineintBruteForce(int l,int r){ //这里不能直接memset不然就不是O(sqrt(n))的了 for (registerint i=l;i<=r;++i) cnt[a[i]]=0; int ret=0; for (registerint i=l;i<=r;++i) { ret=max(ret,org[i]*(++cnt[a[i]])); } return ret; } int c[MAXN],ans; inlinevoidAdd(int x){ ans=max(ans,org[x]*(++c[a[x]])); } inlinevoidDel(int x){ --c[a[x]]; } inlineintMoQueue(int i,int id){//返回下一个块的第一个询问的编号 int R=min(n,Size*id); int l=R,r=R-1; ans=0; memset(c,0,sizeof(c)); while (pos[q[i].l]==id){ if (pos[q[i].l]==pos[q[i].r]) { Ans[q[i].id]=BruteForce(q[i].l,q[i].r); i++; continue; } while (r<q[i].r) Add(++r); int temp=ans;//记录的是[R+1,r]的答案 while (l>q[i].l) Add(--l); Ans[q[i].id]=ans; while (l<R) Del(l++); ans=temp; i++; } return i; } #undef int intmain(){ #define int long long n=read(),m=read(); Size=(int)(sqrt(n)); for (registerint i=1;i<=n;++i){ org[i]=a[i]=read(); pos[i]=(i-1)/Size+1; } discrete(); for (registerint i=1;i<=m;++i){ int l=read(),r=read(); q[i]=Query{l,r,i}; } sort(q+1,q+1+m); int ptr=1; for (registerint i=1;i<=pos[n];++i){ ptr=MoQueue(ptr,i); } for (registerint i=1;i<=m;++i){ printf("%lld\n",Ans[i]); } }