注意到本题数据 $10^5$，于是不用思考性质，直接上分块。时间复杂度 $\Theta(n \sqrt n + m\sqrt n)$。

此题在 Luogu P4168 蒲公英 和 Loj 6285 数列分块入门 9 亦有记载（无性质）。

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <map>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
istream &fin = cin;
ostream &fout = cout;
using ui = unsigned int;
using uli = unsigned long long int;
using li = long long int;
int main(void) {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    size_t n, m;
    if (!(fin >> n >> m)) return 0;
    vector<ui> a(n);
    map<ui, ui> mp;

    for (ui &i : a) {
        int x;
        fin >> x;
        i = x ^ (1u << 31);
        mp.emplace(i, mp.size());
    }


    for (ui &i : a)
        i = mp.at(i);

    constexpr size_t d = 80;
    vector precount{{vector<ui>(mp.size())}};
    precount.reserve(n / d + 1);
    {
        size_t i;

        for (i = 0; i + d < n; i += d) {
            precount.emplace_back(precount.back());

            for (size_t j = i; j < i + d; ++j)
                ++precount.back()[a[j]];
        }
    }
    vector<vector<ui>> bans;
    bans.reserve(n / d + 1);
    {
        size_t i;

        for (i = 0; i + d < n; i += d) {
            bans.emplace_back();
            vector<ui> c(mp.size());
            ++c[a[i]];
            ui ans = a[i];
            size_t j;

            for (j = i + 1; j < n; ++j) {
                if (j % d == 0)
                    bans.back().emplace_back(ans);

                ++c[a[j]];

                if (c[a[j]] > c[ans] || (c[a[j]] == c[ans] && a[j] < ans))
                    ans = a[j];
            }

            bans.shrink_to_fit();
        }
    }

    while (m--) {
        size_t l, r;
        fin >> l >> r;
        --l;
        size_t bl = l / d + 1, br = (r - 1) / d;
        unordered_map<ui, ui> c;

        if (bl >= br)
            for (size_t i = l; i < r; ++i)
                ++c[a[i]];
        else {
            c.emplace(bans[bl][br - bl - 1], precount[br][bans[bl][br - bl - 1]] -
                      precount[bl][bans[bl][br - bl - 1]]);

            for (size_t i = l; i < bl * d; ++i)
                ++c.emplace(a[i], precount[br][a[i]] - precount[bl][a[i]])
                .first->second;

            for (size_t i = br * d; i < r; ++i)
                ++c.emplace(a[i], precount[br][a[i]] - precount[bl][a[i]])
                .first->second;
        }

        fout << ranges::max_element(c,
        [](pair<ui, ui> a, pair<ui, ui> b) {
            return a.second != b.second
                   ? a.second < b.second
                   : a.first > b.first;
        })
        ->second
                << '\n';
    }

    return main();
}