#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long ll;

int const maxn=1e5+;

int n,q,a[maxn],b[maxn],cnt[][maxn],sta[maxn],top,m,tot,blk[maxn],num[maxn];

ll f[][maxn];

int main()

{

    scanf("%d%d",&n,&q); tot=sqrt(n);

    for(int i=;i<=n;i++)blk[i]=(i-)/tot+;

    for(int i=;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];

    sort(b+,b+n+); m=unique(b+,b+n+)-b-;

    for(int i=;i<=n;i++)a[i]=lower_bound(b+,b+m+,a[i])-b;

    for(int i=;i<=blk[n];i++)

    {

        ll nw=;

        for(int j=lower_bound(blk+,blk+n+,i)-blk;j<=n;j++)

            cnt[i][a[j]]++,nw=max(nw,(ll)cnt[i][a[j]]*b[a[j]]),f[i][j]=nw;//cnt是第i块a[j]数量后缀

            //f[i][j]表示第i块到j位置的答案

    }

    for(int i=,x,y;i<=q;i++)

    {

        scanf("%d%d",&x,&y);

        ll ans=f[blk[x]+][y];

        int st=lower_bound(blk+,blk+n+,blk[y])-blk;

        for(int i=st;i<=y;i++)num[a[i]]++,sta[++top]=a[i];

        st=lower_bound(blk+,blk+n+,blk[x]+)-blk;

        for(int i=x;i<st;i++)

        {

            num[a[i]]++;

            ans=max(ans,(ll)(cnt[blk[x]+][a[i]]-cnt[blk[y]][a[i]]+num[a[i]])*b[a[i]]);

            sta[++top]=a[i];

        }

        printf("%lld\n",ans);

        while(top)num[sta[top]]=,top--;//不用memset

    }

    return ;

}