#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Query
{
int l, r, idx;
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
vector<int> cmp(a.begin() + 1, a.end());
sort(cmp.begin(), cmp.end());
cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
vector<int> idx(n + 1);
std::transform(a.begin() + 1, a.end(), idx.begin() + 1, [&cmp](int val)
{ return std::lower_bound(cmp.begin(), cmp.end(), val) - cmp.begin(); });
auto getIndex = [&](int ind)
{
return idx[ind];
};
vector<int> cnt(cmp.size(), 0);
for (int i = 1; i <= n; ++i)
{
cnt[idx[i]]++;
}
vector<ll> importances;
for (int i = 0; i < cmp.size(); ++i)
{
for (int c = 0; c <= cnt[i]; ++c)
{
importances.push_back(ll(c) * cmp[i]);
}
}
sort(importances.begin(), importances.end());
importances.erase(unique(importances.begin(), importances.end()), importances.end());
vector<vector<int>> importanceIdx(cnt.size(), vector<int>());
for (int i = 0; i < cnt.size(); ++i)
{
for (int c = 0; c <= cnt[i]; ++c)
{
auto importance = (ll)c * cmp[i];
importanceIdx[i].push_back(lower_bound(importances.begin(), importances.end(), importance) - importances.begin());
}
}
vector<Query> queries(q);
for (int i = 0; i < q; ++i)
{
cin >> queries[i].l >> queries[i].r;
queries[i].idx = i;
}
int blockSize = sqrt(importances.size()) + 2;
sort(queries.begin(), queries.end(), [&](const Query &a, const Query &b)
{ return a.l / blockSize != b.l / blockSize ? a.l < b.l : a.r < b.r; });
vector<ll> ans(q);
vector<int> sqList(blockSize, 0);
vector<int> importanceCntList(importances.size(), 0);
vector<int> indexCntList(cnt.size(), 0);
auto updateImportance = [&](int importanceIdx, int value)
{
importanceCntList[importanceIdx] += value;
sqList[importanceIdx / blockSize] += value;
};
auto increaseCnt = [&](int idx)
{
int index = getIndex(idx);
int oldCnt = indexCntList[index]++;
updateImportance(importanceIdx[index][oldCnt], -1);
updateImportance(importanceIdx[index][oldCnt + 1], 1);
};
auto decreaseCnt = [&](int idx)
{
int index = getIndex(idx);
int oldCnt = indexCntList[index]--;
updateImportance(importanceIdx[index][oldCnt], -1);
updateImportance(importanceIdx[index][oldCnt - 1], 1);
};
auto getMaxImportance = [&]()
{
for (int i = blockSize - 1; i >= 0; --i)
{
if (sqList[i] > 0)
{
int mini = i * blockSize, maxi = min(n, mini + blockSize);
for (int iter = maxi; iter >= mini; --iter)
{
if (importanceCntList[iter] > 0)
{
return importances[iter];
}
}
}
}
return 0LL;
};
for (int i = 0; i < cnt.size(); ++i)
{
updateImportance(importanceIdx[i][0], 1);
}
int ql = 1, qr = 0;
for (auto query : queries)
{
while (qr < query.r)
increaseCnt(++qr);
while (query.l < ql)
increaseCnt(--ql);
while (query.r < qr)
decreaseCnt(qr--);
while (ql < query.l)
decreaseCnt(ql++);
ans[query.idx] = getMaxImportance();
}
for (auto answer : ans)
{
cout << answer << '\n';
}
}
