// bzoj4241#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;inline LL getint() {    int f,x=0;char ch=getchar();    while (ch<=‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1;else f=1;ch=getchar();}    while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}const int maxn=100010;struct data {int w,id;}a[maxn];int b[maxn],pos[maxn],L[400],R[400],cnt[400][maxn],num[maxn],st[maxn];LL mx[400][400],ans;int n,m,block,tot,top;bool cmp(data a,data b) {    return a.w<b.w;}LL cal(int l,int r) {    LL ans=0;    top=0;    for (int i=l;i<=r;i++) {        if (!num[b[i]]) st[++top]=b[i];        num[b[i]]++;        ans=max(ans,(LL)num[b[i]]*a[b[i]].w);    }    while (top) num[st[top--]]=0;    return ans;}    void build() {    block=sqrt(n);tot=(n-1)/block+1;    for (int i=1;i<=n;i++) {        pos[i]=(i-1)/block+1;        if (!L[pos[i]]) L[pos[i]]=i;        R[pos[i]]=i;    }    for (int i=1;i<=n;i++) cnt[pos[i]][b[i]]++;    for (int i=2;i<=tot;i++)        for (int j=1;j<=n;j++) cnt[i][j]+=cnt[i-1][j];}int main() {    scanf("%d%d",&n,&m);    for (int i=1;i<=n;i++) scanf("%d",&a[i].w),a[i].id=i;    sort(a+1,a+1+n,cmp);    b[a[1].id]=1;    for (int i=2;i<=n;i++) {        if (a[i].w==a[i-1].w) b[a[i].id]=b[a[i-1].id];        else b[a[i].id]=i;    }    build();    for (int i=1;i<=tot;i++) {        LL ans=0;        memset(num,0,sizeof(num));        for (int j=L[i];j<=n;j++) {            num[b[j]]++;            ans=max(ans,(LL)num[b[j]]*a[b[j]].w);            if (j==R[pos[j]]) mx[i][pos[j]]=ans;        }    }    memset(num,0,sizeof(num));    for (int i=1;i<=m;i++) {        int l,r;        scanf("%d%d",&l,&r);        ans=0;        if (pos[l]==pos[r]) printf("%lld\n",cal(l,r));        else {            ans=mx[pos[l]+1][pos[r]-1];            top=0;            for (int i=l;i<=R[pos[l]];i++)                if (!num[b[i]]) st[++top]=b[i],num[b[i]]=cnt[pos[r]-1][b[i]]-cnt[pos[l]][b[i]];            for (int i=L[pos[r]];i<=r;i++)                if (!num[b[i]]) st[++top]=b[i],num[b[i]]=cnt[pos[r]-1][b[i]]-cnt[pos[l]][b[i]];            for (int i=l;i<=R[pos[l]];i++) num[b[i]]++;            for (int i=L[pos[r]];i<=r;i++) num[b[i]]++;            while (top) {                ans=max(ans,(LL)a[st[top]].w*num[st[top]]);                num[st[top--]]=0;            }            printf("%lld\n",ans);        }    }    return 0;}