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

const int MAXN = 200005;
int N, Q, A[MAXN];
vector<int> answer;

struct Query {
    int l, r, idx;
    bool operator<(const Query &other) const {
        int block_a = l / sqrt(N);
        int block_b = other.l / sqrt(N);
        if (block_a != block_b) return block_a < block_b;
        return (block_a & 1) ? (r < other.r) : (r > other.r);
    }
};

void processQueries(vector<Query>& queries) {
    int freq[MAXN] = {0};
    int current_l = 0, current_r = -1;
    for (auto &query : queries) {
        while (current_r < query.r) {
            current_r++;
            freq[A[current_r]]++;
        }
        while (current_r > query.r) {
            freq[A[current_r]]--;
            current_r--;
        }
        while (current_l < query.l) {
            freq[A[current_l]]--;
            current_l++;
        }
        while (current_l > query.l) {
            current_l--;
            freq[A[current_l]]++;
        }

        int threshold = (query.r - query.l + 1) / 3;
        int min_val = INT_MAX;
        for (int i = current_l; i <= current_r; i++) {
            if (freq[A[i]] > threshold) min_val = min(min_val, A[i]);
        }

        answer[query.idx] = (min_val == INT_MAX) ? -1 : min_val;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> Q;
    for (int i = 0; i < N; i++) cin >> A[i];

    vector<Query> queries(Q);
    answer.resize(Q);
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        queries[i] = {l - 1, r - 1, i};  // 0-indexed
    }

    sort(queries.begin(), queries.end());
    processQueries(queries);

    for (int i = 0; i < Q; i++) {
        cout << answer[i] << "\n";
    }

    return 0;
}