#include<stdio.h>
#include<map>
int imp[100501];
int impNum[100501];
int num[100501];
int dp[330][330];
int cnt[330][100001];
int chk[100001];
int main()
{
int n, r, q, impC = 0;
scanf("%d%d", &n, &q);
for(int i=1; i<=n; i++) scanf("%d", &imp[i]);
std::map<int, int> A;
for(int i=1; i<=n; i++)
{
if(A.find(imp[i]) == A.end())
{
A.insert(std::make_pair(imp[i], ++impC));
num[i] = impC;
impNum[impC] = imp[i];
}
else
{
num[i] = A[imp[i]];
}
}
for(r=1; r*r < n; r++);
for(int i=1; i<=r; i++)
{
for(int j=1; j<=r; j++)
{
int t = i*r - r + j;
if(num[t] == 0) break;
for(int k=i; k<=r; k++) cnt[k][num[t]] ++;
}
}
for(int i=1; i<=r; i++)
{
for(int j=i; j<=r; j++)
{
dp[i][j] = dp[i][j-1];
for(int k=1; k<=r; k++)
{
int t = num[j*r - r + k];
if(1ll*impNum[t]*(cnt[j][t]-cnt[i-1][t]) > 1ll*impNum[dp[i][j]]*(cnt[j][dp[i][j]]-cnt[i-1][dp[i][j]]))
dp[i][j] = t;
}
}
}
for(int Q=1; Q<=q; Q++)
{
int s, f, a, b;
scanf("%d%d", &a, &b);
s = a; f = b;
if(s==1) s=1;
else
{
s-=2;
s/=r;
s+=2;
}
if(f==n) f = r;
else
f/=r;
long long max = 0;
if(s<=f)
{
max = 1ll*impNum[dp[s][f]]*(cnt[f][dp[s][f]] - cnt[s-1][dp[s][f]]);
for(int i=a; i<=s*r-r; i++)
{
chk[num[i]] ++;
if(1ll * imp[i] * (chk[num[i]] + cnt[f][num[i]] - cnt[s-1][num[i]]) > max)
max = 1ll * imp[i] * (chk[num[i]] + cnt[f][num[i]] - cnt[s-1][num[i]] );
}
for(int i=f*r+1; i<=b; i++)
{
chk[num[i]] ++;
if(1ll * imp[i] * (chk[num[i]] + cnt[f][num[i]] - cnt[s-1][num[i]]) > max)
max = 1ll * imp[i] * (chk[num[i]] + cnt[f][num[i]] - cnt[s-1][num[i]] );
}
for(int i=a; i<=s*r-r; i++) chk[num[i]] = 0;
for(int i=f*r+1; i<=b; i++) chk[num[i]] = 0;
}
else
{
for(int i=a; i<=b; i++)
{
chk[num[i]] ++;
if(1ll * imp[i] * chk[num[i]] > max)
max = 1ll * imp[i] * chk[num[i]];
}
for(int i=a; i<=b; i++) chk[num[i]] = 0;
}
printf("%lld\n", max);
}
return 0;
}
