#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> comp(a.begin() + 1, a.end());
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
vector<int> idx(n + 1);
for (int i = 1; i <= n; ++i)
{
idx[i] = int(lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin());
}
auto getIdx = [&](int x)
{ return idx[x]; };
int m = comp.size();
vector<int> tot(m, 0);
for (int i = 1; i <= n; i++)
{
tot[getIdx(i)]++;
}
vector<vector<int>> impMap(m);
vector<ll> impList;
for (int t = 0; t < m; t++)
{
impMap[t].resize(tot[t] + 1);
for (int k = 0; k <= tot[t]; k++)
{
impList.push_back((ll)comp[t] * k);
}
}
sort(impList.begin(), impList.end());
impList.erase(unique(impList.begin(), impList.end()), impList.end());
for (int t = 0; t < m; t++)
{
for (int k = 0; k <= tot[t]; k++)
{
ll val = (ll)comp[t] * k;
impMap[t][k] = int(lower_bound(impList.begin(), impList.end(), val) - impList.begin());
}
}
int block = sqrt(n) + 1;
vector<Query> qs(q);
for (int i = 0; i < q; i++)
{
int L, R;
cin >> L >> R;
qs[i] = {L, R, i};
}
sort(qs.begin(), qs.end(), [&](const Query &A, const Query &B)
{
if(A.l/block != B.l/block) return A.l < B.l;
return A.r < B.r; });
vector<int> freq(m, 0);
int impSize = impList.size();
vector<int> cnt(impSize, 0);
vector<int> sqCnt(block, 0);
auto upd = [&](int pos, int d)
{
cnt[pos] += d;
sqCnt[pos / block] += d;
};
auto add = [&](int idx)
{
int t = getIdx(idx);
int old = freq[t]++;
upd(impMap[t][old], -1);
upd(impMap[t][old + 1], 1);
};
auto remove = [&](int idx)
{
int t = getIdx(idx);
int old = freq[t]--;
upd(impMap[t][old], -1);
upd(impMap[t][old - 1], 1);
};
auto getMax = [&]()
{
for (int b = block - 1; b >= 0; b--)
{
if (sqCnt[b] > 0)
{
int start = b * block, end = min(impSize, start + block);
for (int i = end - 1; i >= start; i--)
{
if (cnt[i])
return impList[i];
}
}
}
return 0LL;
};
for (int t = 0; t < m; t++)
{
upd(impMap[t][0], 1);
}
int curL = 1, curR = 0;
vector<ll> ans(q, 0);
for (auto &qu : qs)
{
while (curR < qu.r)
add(++curR);
while (curR > qu.r)
remove(curR--);
while (curL < qu.l)
remove(curL++);
while (curL > qu.l)
add(--curL);
ans[qu.idx] = getMax();
}
for (auto x : ans)
cout << x << "\n";
return 0;
}
