#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9,SqrtN = 359;
int n,q;
int a[N];
int tmp[N],top;
struct block{
	int l,r;
} b[SqrtN];
int block_len,block_cnt;
int belong[N];
void build_block(){
	block_len = block_cnt = sqrt(n);
	for(int i = 1;i <= block_cnt;i++){
		b[i].l = b[i - 1].r + 1;
		b[i].r = b[i].l + block_len - 1;
	}
	b[block_cnt].r = n;
	for(int i = 1;i <= block_cnt;i++)
		for(int j = b[i].l;j <= b[i].r;j++)
			belong[j] = i;
}
int s[SqrtN][N];//前i个块中每个事件类型的出现次数
int p[SqrtN][SqrtN];//第i~j个块中最重要的事件类型的重要程度
int bucket[N];
void init(){
	for(int i = 1;i <= block_cnt;i++){
		for(int j = 1;j <= top;j++)
			s[i][j] = s[i - 1][j];
		for(int j = b[i].l;j <= b[i].r;j++)
			s[i][a[j]]++;
	}
	for(int i = 1;i <= block_cnt;i++){
		for(int j = i;j <= block_cnt;j++){
			for(int k = b[j].l;k <= b[j].r;k++){
				bucket[a[k]]++;
				p[i][j] = max(p[i][j],bucket[a[k]] * tmp[a[k]]);
			}
		}
		memset(bucket,0,sizeof bucket);
	}
}
int query(int l,int r){
	int pos_l = belong[l],pos_r = belong[r];
	int ret = 0;
	if(pos_l == pos_r){
		for(int i = l;i <= r;i++){
			bucket[a[i]]++;
			ret = max(ret,bucket[a[i]] * tmp[a[i]]);
		}
		//清空
		for(int i = l;i <= r;i++)
			bucket[a[i]] = 0;
		return ret;
	}
	ret = p[pos_l + 1][pos_r - 1];
	for(int i = l;i <= b[pos_l].r;i++){
		bucket[a[i]]++;
		ret = max(ret,(bucket[a[i]] + s[pos_r - 1][a[i]] - s[pos_l][a[i]]) * tmp[a[i]]);
	}
	for(int i = b[pos_r].l;i <= r;i++){
		bucket[a[i]]++;
		ret = max(ret,(bucket[a[i]] + s[pos_r - 1][a[i]] - s[pos_l][a[i]]) * tmp[a[i]]);
	}
	
	//清空
	for(int i = l;i <= b[pos_l].r;i++)
		bucket[a[i]] = 0;
	for(int i = b[pos_r].l;i <= r;i++)
		bucket[a[i]] = 0;
	return ret;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> q;
	build_block();
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		tmp[++top] = a[i];
	}
	sort(tmp + 1,tmp + top + 1);
	top = unique(tmp + 1,tmp + top + 1) - tmp - 1;
	for(int i = 1;i <= n;i++)
		a[i] = lower_bound(tmp + 1,tmp + top + 1,a[i]) - tmp;
	init();
	while(q--){
		int l,r;
		cin >> l >> r;
		cout << query(l,r) << '\n';
	}
	return 0;
}