#include<cstdio>
#include<memory.h>
#include<algorithm>
int a[100000];
int b[100000];
int c[100000];
int d[500][100000];
long long x[500][500];
char ss[2097152];
inline int getnum()
{
int t,r=0;
do{t=getchar();}while(t<40);
do{r=r*10+t-48;t=getchar();}while(t>40);
return r;
}
int main()
{
char *p;
long long r;
int s,e,t;
int i,j,k,n,m;
scanf("%d %d\n",&n,&m);
fgets(ss,2097151,stdin);
p=ss;
for(i=0;i<n;i++)
{
while(*p<40)p++;
while(*p>40)
{
a[i]=a[i]*10+*p-48;
p++;
}
b[i]=a[i];
}
std::sort(b,b+n);
for(i=0;i<n;i++)a[i]=std::lower_bound(b,b+n,a[i])-b;
for(i=0;i<n;i++)
{
if(i>0&&(i&255)==0)memcpy(d[i>>8],d[(i>>8)-1],n<<2);
d[i>>8][a[i]]++;
}
for(i=0;i<(n>>8);i++)
{
memset(c,0,n<<2);
for(j=i;j<(n>>8);j++)
{
if(j>i)x[i][j]=x[i][j-1];
for(k=0;k^256;k++)
{
t=(j<<8)|k;
c[a[t]]++;
if(1LL*b[a[t]]*c[a[t]]>x[i][j])x[i][j]=1LL*b[a[t]]*c[a[t]];
}
}
}
memset(c,0,n<<2);
for(i=0;i<m;i++)
{
s=getnum()-1;e=getnum();
if(((~-s)>>8)+1<(e>>8))
{
r=x[((~-s)>>8)+1][(e>>8)-1];
for(j=s;j<(((~-s)>>8)+1<<8);j++)
{
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[(e>>8)-1][a[j]]-(((~-s)>>8)+1>0?d[(~-s)>>8][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[(e>>8)-1][a[j]]-(((~-s)>>8)+1>0?d[(~-s)>>8][a[j]]:0));
}
for(j=((e>>8)<<8);j<e;j++)
{
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[(e>>8)-1][a[j]]-(((~-s)>>8)+1>0?d[(~-s)>>8][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[(e>>8)-1][a[j]]-(((~-s)>>8)+1>0?d[(~-s)>>8][a[j]]:0));
}
for(j=s;j<(((~-s)>>8)+1<<8);j++)c[a[j]]=0;
for(j=((e>>8)<<8);j<e;j++)c[a[j]]=0;
}
else
{
r=0;
for(j=s;j<e;j++)
{
c[a[j]]++;
if(1LL*b[a[j]]*c[a[j]]>r)r=1LL*b[a[j]]*c[a[j]];
}
for(j=s;j<e;j++)c[a[j]]=0;
}
printf("%lld\n",r);
}
}
