#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX = 100020, GROUP_SIZE = 350;
struct query {
int s, e, index;
int getStartGroup() const {
return s/GROUP_SIZE+1;
}
bool operator < (const query &t) const {
int g1 = getStartGroup(), g2 = t.getStartGroup();
if (g1 == g2)
return e < t.e;
return g1 < g2;
}
};
int numEvent, numQuery, qFull, impact[MAX], xList[MAX], xFull;
query queries[MAX];
ll ans[MAX];
int cnt[MAX];
void input() {
scanf("%d%d", &numEvent, &numQuery);
for (int i = 0; i < numEvent; i++) {
scanf("%d", &impact[i]);
xList[xFull++] = impact[i];
}
sort(xList, xList+xFull);
xFull = unique(xList, xList+xFull)-xList;
// renumbering
for (int i = 0; i < numEvent; i++) {
impact[i] = lower_bound(xList, xList+xFull, impact[i]) - xList;
}
for (int i = 0; i < numQuery; i++) {
int f, s;
scanf("%d%d", &f, &s);
// Convert to 0-base
queries[qFull].s = f-1;
queries[qFull].e = s-1;
queries[qFull].index = i;
if (queries[qFull].e < queries[qFull].getStartGroup() * GROUP_SIZE) {
// Calculate immediately
ll tAns = 0;
query &now = queries[qFull];
for (int i = now.s; i <= now.e; i++) {
int tImpact = impact[i];
cnt[tImpact]++;
tAns = max(tAns, (ll)cnt[tImpact] * xList[tImpact]);
}
for (int i = now.s; i <= now.e; i++) {
int tImpact = impact[i];
cnt[tImpact]--;
}
ans[i] = tAns;
} else
// Put into a queue
qFull++;
}
sort(queries, queries+qFull);
}
void solve() {
int currentQuery = 0;
while (currentQuery < qFull) {
// Init count
for (int i = 0; i < xFull; i++)
cnt[i] = 0;
ll maxInRange = 0;
int startGroup = queries[currentQuery].getStartGroup(), startIndex = startGroup * GROUP_SIZE;
for (int lastEvent = startIndex; lastEvent < numEvent; lastEvent++) {
int tImpact = impact[lastEvent];
cnt[tImpact]++;
maxInRange = max(maxInRange, (ll)cnt[tImpact] * xList[tImpact]);
if (startGroup < queries[currentQuery].getStartGroup()) break;
else {
while (startGroup == queries[currentQuery].getStartGroup()
&& currentQuery < qFull && lastEvent == queries[currentQuery].e) {
ll tAns = maxInRange;
query &now = queries[currentQuery];
for (int i = now.s; i < startIndex; i++) {
tImpact = impact[i];
cnt[tImpact]++;
tAns = max(tAns, (ll)cnt[tImpact] * xList[tImpact]);
}
for (int i = now.s; i < startIndex; i++) {
tImpact = impact[i];
cnt[tImpact]--;
}
ans[now.index] = tAns;
currentQuery++;
}
}
}
}
}
void print() {
for (int i = 0; i < numQuery; i++)
printf("%lld\n", ans[i]);
}
int main() {
input();
solve();
print();
return 0;
}
