BZ4241

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c))x=x*10+c-'0',gc;x*=k;
}

const int N=1e5+7;
const int S=320;

int a[N];
int be[N];
int val[N];
int cnt[N];
ll Ans[N];
int L[S];
int R[S];

struct Query{
    int l,r,id;
    inline bool operator < (const Query &a)const{
        return be[l]==be[a.l]?r<a.r:l<a.l;
    }
}Q[N];

int n,q;
ll ans;

inline void add(int x){
    cnt[x]++;
    ans=max(ans,(ll)cnt[x]*val[x]);
}

inline void del(int x){
    cnt[x]--;
}

int tmp[N];

inline ll solve(int l,int r){
    ll ret=0;
    for(int i=l;i<=r;++i)tmp[a[i]]=0;
    for(int i=l;i<=r;++i)tmp[a[i]]++;
    for(int i=l;i<=r;++i)ret=max(ret,(ll)tmp[a[i]]*val[a[i]]);
    return ret;
}

inline void Get(int x,int &i){
    int l=R[x]+1,r=R[x];
    memset(cnt+1,0,n<<2);
    for(ans=0;be[Q[i].l]==x;++i){
        if(be[Q[i].r]==x){
            Ans[Q[i].id]=solve(Q[i].l,Q[i].r);
            continue;
        }
        while(r<Q[i].r)add(a[++r]);
        ll t=ans;
        while(l>Q[i].l)add(a[--l]);
        Ans[Q[i].id]=ans;
        while(l<R[x]+1)del(a[l++]);
        ans=t;
    }
}

int main(){
    r(n),r(q);
    const int SIZE=sqrt(n);
    for(int i=1;i<=n;++i){
        r(a[i]);
        be[i]=(i-1)/SIZE+1;
        if(!L[be[i]])L[be[i]]=i;
        R[be[i]]=i;
        val[i]=a[i];
    }
    sort(val+1,val+n+1);
    for(int i=1;i<=n;++i){
        a[i]=lower_bound(val+1,val+n+1,a[i])-val;
    }
    for(int i=1;i<=q;++i){
        r(Q[i].l),r(Q[i].r);
        Q[i].id=i;
    }
    sort(Q+1,Q+q+1);
    for(int i=1,x=1;i<=q;++x){
        Get(x,i);
    }
    for(int i=1;i<=q;++i){
        printf("%lld\n",Ans[i]);
    }
}