#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;
const int N = 1e5 + 15;
int a[N];
int uniqueValueIdx[N];
ll importances[N];
vector<int> getUniqueValues(int n)
{
vector<int> uniqueValues(n);
for (int i = 1; i <= n; ++i)
{
uniqueValues[i - 1] = a[i];
}
sort(uniqueValues.begin(), uniqueValues.end());
uniqueValues.erase(unique(uniqueValues.begin(), uniqueValues.end()), uniqueValues.end());
return uniqueValues;
}
void calculateUniqueValueIdx(int n)
{
vector<int> uniqueValues = getUniqueValues(n);
for (int i = 1; i <= n; ++i)
{
uniqueValueIdx[i] = lower_bound(uniqueValues.begin(), uniqueValues.end(), a[i]) - uniqueValues.begin();
}
}
vector<int> importanceIdx[N];
void calculateImportance(int n)
{
importances[0] = 0;
vector<int> cnt(n + 1, 0);
for (int i = 1; i <= n; ++i)
{
int id = uniqueValueIdx[i];
++cnt[id];
importances[i] = (ll)cnt[id] * a[i];
}
sort(importances, importances + n + 1);
int uniqueImportanceSize = unique(importances, importances + n + 1) - importances;
for (int i = 1; i <= n; ++i)
{
int id = uniqueValueIdx[i];
if (importanceIdx[id].empty())
{
importanceIdx[id].push_back(0);
}
}
fill(cnt.begin(), cnt.end(), 0);
for (int i = 1; i <= n; ++i)
{
int id = uniqueValueIdx[i];
++cnt[id];
int importanceIndex = lower_bound(importances, importances + uniqueImportanceSize, (ll)cnt[id] * a[i]) - importances;
importanceIdx[id].push_back(importanceIndex);
}
}
const int SQ = 400;
struct Query
{
int l, r, idx;
bool operator<(const Query &other) const
{
return r < other.r;
}
};
vector<Query> queries[SQ];
void processQuery(int n, int m)
{
for (int i = 0; i < m; ++i)
{
int x, y;
scanf("%d %d", &x, &y);
queries[x / SQ].push_back({x, y, i});
}
vector<int> cnt(n + 1, 0);
vector<int> sqCnt(SQ, 0);
auto add = [&](int idx)
{
++cnt[idx];
++sqCnt[idx / SQ];
};
auto remove = [&](int idx)
{
--cnt[idx];
--sqCnt[idx / SQ];
};
auto findAnswer = [&]() -> ll
{
for (int i = SQ - 1; i >= 0; --i)
{
if (sqCnt[i] > 0)
{
int maxi = min(i * SQ + (SQ - 1), n);
int mini = i * SQ;
for (int j = maxi; j >= mini; --j)
{
if (cnt[j] > 0)
{
return importances[j];
}
}
}
}
return 0LL;
};
for (int i = 0; i < SQ; ++i)
{
sort(queries[i].begin(), queries[i].end());
}
for (int i = 1; i <= n; ++i)
{
add(0);
}
int ql = 1, qr = 0;
vector<ll> ans(m);
vector<int> cnt2(n + 1, 0);
for (int i = 0; i < SQ; ++i)
{
for (auto &query : queries[i])
{
int l = query.l, r = query.r;
while (qr < r)
{
int id = uniqueValueIdx[++qr];
int importIdx = importanceIdx[id][cnt2[id]];
remove(importIdx);
++cnt2[id];
importIdx = importanceIdx[id][cnt2[id]];
add(importIdx);
}
while (l < ql)
{
int id = uniqueValueIdx[--ql];
int importIdx = importanceIdx[id][cnt2[id]];
remove(importIdx);
++cnt2[id];
importIdx = importanceIdx[id][cnt2[id]];
add(importIdx);
}
while (r < qr)
{
int id = uniqueValueIdx[qr--];
int importIdx = importanceIdx[id][cnt2[id]];
remove(importIdx);
--cnt2[id];
importIdx = importanceIdx[id][cnt2[id]];
add(importIdx);
}
while (ql < l)
{
int id = uniqueValueIdx[ql++];
int importIdx = importanceIdx[id][cnt2[id]];
remove(importIdx);
--cnt2[id];
importIdx = importanceIdx[id][cnt2[id]];
add(importIdx);
}
ans[query.idx] = findAnswer();
}
}
for (int i = 0; i < m; ++i)
{
printf("%lld\n", ans[i]);
}
}
void solve2()
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
}
calculateUniqueValueIdx(n);
calculateImportance(n);
processQuery(n, m);
}
void solve()
{
// init();
// int t;
// scanf("%d",&t);
// while(t--)
solve2();
}
int main()
{
// cin,cout fast
// ios_base::sync_with_stdio(false);
solve();
return 0;
}
