65pts求调

#include <bits/stdc++.h>
#define pb push_back
#define pf(a) push_front(a)
#define pof pop_front
#define pob pop_back
#define fr() front()
#define ba() back()
#define ls(x) x << 1
#define rs(x) (x << 1) | 1
#define re register
#define in(a) insert(a)
#define fi first
#define se second
#define gcd(a, b) __gcd(a, b)
#define l2(a) log(a) / log(2)
#define ui128 unsigned __int128
#define ll long long
#define pll pair<ll, ll>
#define ull unsigned long long
#define pii pair<int, int>
#define pq1 priority_queue<int>
#define pq2 priority_queue<int, vector<int>, greater<int>>
#define ui unsigned int
#define db double
#define Add1(u,v) g[u].pb(v)
#define Add2(u,v,w) g[u].pb({v,w})
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

int n, q;
vector<int> a;
map<int, vector<int>> pos;

signed main() {
    IOS;
    cin >> n >> q;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pos[a[i]].pb(i);
    }
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        int len = r - l + 1;
        int k = len / 2;
        int found = -1;
        for (int iter = 0; iter < 30; iter++) {
            int idx = uniform_int_distribution<int>(l, r)(rng);
            int val = a[idx];
            const auto& v = pos[val];
            int cnt = upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l);
            if (cnt > k) {
                found = val;
                break;
            }
        }
        if (found == -1) {
            cout << 0 << "\n";
        } else {
            cout << found << "\n";
        }
    }
    return 0;
}