// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
// #include <unordered_set>
// #include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>

using namespace std;

#define y1 y11
#define left left228
#define right right228
#define list list228
#define all(v) v.begin(), v.end()
#define tm tm228
#define free free228



template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}

const int N = 500 * 1000 + 228;
const int C = 25;

int n, q;
int a[N], allcnt[N];
vector<int> pos[N];
mt19937 rnd(rand());
bool used[N];

int get(int x, int l, int r) {
    return upper_bound(all(pos[x]), r) - lower_bound(all(pos[x]), l);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ++allcnt[a[i]];
        pos[a[i]].emplace_back(i);
    }
    int l, r, len;
    int p = 0;
    vector<int> bad;
    bad.reserve(N);
    while(q--) {
        cin >> l >> r;
        len = r - l + 1;
        bad.clear();
        int ans = 0;
        for (int it = 0; it < C; ++it) {
            p = l + rnd() % (r - l + 1);
            if (!used[a[p]] && allcnt[a[p]] * 2 > len) {
                if (get(a[p], l, r) * 2 > len) {
                    ans = a[p];
                    break;
                }
                used[a[p]]=1;
                bad.emplace_back(a[p]);
            }
        }
        for (int x : bad) {
            used[x] = 0;
        }
        cout << ans << '\n';
    }
    return 0;
}

// RU_023

/*

5 11
?
+ 1 2
+ 2 3
+ 3 4
+ 4 5
+ 5 1
?
- 2 3
?
- 4 5
?


*/