#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> l(q), r(q);
for (int i = 0; i < q; i++) {
cin >> l[i] >> r[i];
--l[i]; --r[i];
}
vector<int> xs;
for (int i = 0; i < n; i++) {
xs.push_back(a[i]);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
for (int i = 0; i < n; i++) {
a[i] = (int) (lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin());
}
int k = (int) xs.size();
const int BLOCK = 100;
vector<int> cnt(k);
for (int i = 0; i < n; i++) {
cnt[a[i]] += 1;
}
vector<long long> res(q);
for (int v = 0; v < k; v++) {
if (cnt[v] < BLOCK) {
continue;
}
vector<int> pref(n);
for (int i = 0; i < n; i++) {
if (i > 0) {
pref[i] = pref[i - 1];
}
pref[i] += (a[i] == v);
}
for (int i = 0; i < q; i++) {
int s = pref[r[i]] - (l[i] > 0 ? pref[l[i] - 1] : 0);
res[i] = max(res[i], s * 1LL * xs[v]);
}
}
vector<vector<int>> qs(n);
for (int i = 0; i < q; i++) {
qs[r[i]].push_back(i);
}
vector<long long> fenw(n + 1);
auto Modify = [&](int p, long long v) {
for (p++; p <= n; p += p & -p) {
fenw[p] = max(fenw[p], v);
}
};
auto Query = [&](int p) {
long long ret = 0;
for (p++; p; p -= p & -p) {
ret = max(ret, fenw[p]);
}
return ret;
};
vector<vector<int>> pos(k);
for (int i = 0; i < n; i++) {
if (cnt[a[i]] < BLOCK) {
pos[a[i]].push_back(i);
int sz = (int) pos[a[i]].size();
for (int j = 0; j < sz; j++) {
Modify(n - pos[a[i]][j] - 1, (sz - j) * 1LL * xs[a[i]]);
}
}
for (int j : qs[i]) {
res[j] = max(res[j], Query(n - l[j] - 1));
}
}
for (int i = 0; i < q; i++) {
cout << res[i] << '\n';
}
return 0;
}
