#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#include <ranges>
#define ll long long
using namespace std;
vector<int> getAIdx(vector<int> &a)
{
int n = a.size() - 1;
unordered_map<int, int> idxMap;
vector<int> aIdx(n + 1, 0);
for (int i = 1, idxPos = 0; i <= n; ++i)
{
if (!idxMap.count(a[i]))
{
idxMap[a[i]] = idxPos++;
}
aIdx[i] = idxMap[a[i]];
}
return aIdx;
}
vector<ll> getImportanceList(vector<int> &a)
{
int n = a.size() - 1;
vector<int> cnt(n + 1, 0);
vector<ll> importance(n + 1, 0);
auto aIdx = getAIdx(a);
for (int i = 1; i <= n; ++i)
{
++cnt[aIdx[i]];
importance[i] = (ll)cnt[aIdx[i]] * a[i];
}
sort(importance.begin(), importance.end());
return importance;
}
struct pair_hash
{
template <class T1, class T2>
std::size_t operator()(const std::pair<T1, T2> &p) const
{
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
return h1 ^ (h2 << 1);
}
};
unordered_map<pair<int, int>, int, pair_hash> calculateImportance(vector<int> &a)
{
int n = a.size() - 1;
auto importanceList = getImportanceList(a);
unordered_map<pair<int, int>, int, pair_hash> importanceMap;
auto aIdx = getAIdx(a);
vector<int> cnt(n + 1, 0);
for (int i = 1; i <= n; ++i)
{
++cnt[aIdx[i]];
importanceMap[{aIdx[i], cnt[aIdx[i]]}] =
lower_bound(importanceList.begin(), importanceList.end(), (ll)cnt[aIdx[i]] * a[i]) - importanceList.begin();
}
for (int i = 1; i <= n; ++i)
{
importanceMap[{aIdx[i], 0}] = 0;
}
return importanceMap;
}
const int SQ = 400;
struct Query
{
int l, r, idx;
bool operator<(const Query &other) const
{
if (l / SQ != other.l / SQ)
{
return l < other.l;
}
else
{
return r < other.r;
}
}
};
void processQuery(vector<int> &a, int m)
{
int n = a.size() - 1;
auto aIdx = getAIdx(a);
auto importanceList = getImportanceList(a);
auto importanceMap = calculateImportance(a);
vector<Query> queries(m);
for (int i = 0; i < m; ++i)
{
scanf("%d %d", &queries[i].l, &queries[i].r);
queries[i].idx = i;
}
sort(queries.begin(), queries.end());
vector<int> idxCnt(n + 1, 0);
vector<int> sqCnt(SQ + 1, 0);
vector<int> importanceCnt(n + 1, 0);
auto increaseValue = [&](int idx)
{
int valueIndex = aIdx[idx];
int importIdx = importanceMap[{valueIndex, idxCnt[valueIndex]}];
if (importIdx != 0)
{
--importanceCnt[importIdx];
--sqCnt[importIdx / SQ];
}
++idxCnt[valueIndex];
importIdx = importanceMap[{valueIndex, idxCnt[valueIndex]}];
++importanceCnt[importIdx];
++sqCnt[importIdx / SQ];
};
auto decreaseValue = [&](int idx)
{
int valueIndex = aIdx[idx];
int importIdx = importanceMap[{valueIndex, idxCnt[valueIndex]}];
--importanceCnt[importIdx];
--sqCnt[importIdx / SQ];
--idxCnt[valueIndex];
importIdx = importanceMap[{valueIndex, idxCnt[valueIndex]}];
if (importIdx != 0)
{
++importanceCnt[importIdx];
++sqCnt[importIdx / SQ];
}
};
auto getMaxImportance = [&]() -> ll
{
for (int sqIter = SQ - 1; sqIter >= 0; --sqIter)
{
if (sqCnt[sqIter] > 0)
{
int maxi = min(n, SQ * (sqIter + 1));
for (int i = maxi; i >= 0; --i)
{
if (importanceCnt[i] > 0)
{
return importanceList[i];
}
}
}
}
return 0LL;
};
vector<ll> ans(m);
int ql = 1, qr = 0;
for (auto query : queries)
{
while (qr < query.r)
{
increaseValue(++qr);
}
while (query.l < ql)
{
increaseValue(--ql);
}
while (query.r < qr)
{
decreaseValue(qr--);
}
while (ql < query.l)
{
decreaseValue(ql++);
}
ans[query.idx] = getMaxImportance();
}
for (int i = 0; i < m; ++i)
{
printf("%lld\n", ans[i]);
}
}
void solve2()
{
int n, m;
scanf("%d %d", &n, &m);
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
}
processQuery(a, m);
}
int main()
{
solve2();
return 0;
}
