// 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;

}