#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("vpt")
#pragma GCC optimize("Ofast")
mt19937 rnd(27292);
//#define int long long
#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define firn(i, n) for (int i = 1; i < (int)n; i++)
#define all(v) v.begin(), v.end()
//const long long mod = 998244353;
//int MAX = 30000;
const int N = 500'005, C = 22;
vector<int> b[N];
int used[N];
signed main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    forn(i, n) {
        cin >> a[i];
        b[a[i]].push_back(i);
    }
    vector<int> tt(C);
    forn(i, C) tt[i] = rnd();
    firn(w, q + 1) {
        int l, r;
        cin >> l >> r;
        l--;
        int ans = 0, sz = (r - l) / 2;
        forn(z, C) {
            int c = a[rnd() % (r - l) + l];
            if (used[c] < w && (int)b[c].size() * 2 > r - l) {
                used[c] = w;
                int x1 = lower_bound(all(b[c]), l) - b[c].begin() - 1;
                if (b[c].size() > x1 + sz + 1 && b[c][x1 + sz + 1] < r) {
                    ans = c;
                    break;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}