注意到数据 $10^5$，于是不用思考性质，直接上莫队。时间复杂度 $\Theta(n\sqrt{m})$。

此题在 P3709 亦有记载（无性质）。

#include <bits/stdc++.h>
using namespace std;

struct query {
  size_t l, r, id;
};

struct mo {
  uint32_t mx;
  vector<uint32_t> num, cnt;
  mo(size_t n) : mx(0), num(n + 1), cnt(n + 1) { cnt[0] = UINT32_MAX; }
  inline void add(size_t x) {
    --cnt[num[x]];
    ++cnt[++num[x]];
    if (num[x] > mx)
      mx = num[x];
  }
  inline void erase(size_t x) {
    if (mx == num[x] && cnt[num[x]] == 1)
      --mx;
    --cnt[num[x]];
    ++cnt[--num[x]];
  }
  inline uint32_t query() { return mx; }
};

int solve() {
  size_t n, m;
  cin >> n;
  if (n == 0)
    return 0;
  cin >> m;
  size_t bs = max(n / max(sqrt(m), 1.0), 1.0);
  vector<uint32_t> arr(n);
  unordered_map<uint32_t, uint32_t> mp;
  mp.reserve(n * 1.3);
  for (size_t i = 0; i < n; ++i) {
    cin >> arr[i];
    if (!mp.count(arr[i]))
      mp[arr[i]] = mp.size();
    arr[i] = mp[arr[i]];
  }
  vector<vector<query>> queries((n - 1) / bs + 1);
  for (size_t i = 0; i < m; ++i) {
    query q;
    cin >> q.l >> q.r;
    --q.l, q.id = i;
    queries[q.l / bs].push_back(q);
  }
  auto even_cmp = [](const query &a, const query &b) { return a.r < b.r; };
  auto odd_cmp = [](const query &a, const query &b) { return a.r > b.r; };
  mo mo(n);
  uint32_t l = 0, r = 0;
  vector<uint32_t> ans(m);
  for (size_t i = 0; i < queries.size(); ++i) {
    sort(queries[i].begin(), queries[i].end(), i & 1 ? odd_cmp : even_cmp);
    for (const auto &q : queries[i]) {
      while (l > q.l)
        mo.add(arr[--l]);
      while (r < q.r)
        mo.add(arr[r++]);
      while (l < q.l)
        mo.erase(arr[l++]);
      while (r > q.r)
        mo.erase(arr[--r]);
      ans[q.id] = mo.query();
    }
  }
  for (const auto &x : ans)
    cout << x << '\n';
  return 1;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  while (solve())
    ;
  return 0;
}