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

struct Query {
    int l, r, idx;
    Query(int left, int right, int index) : l(left), r(right), idx(index) {}
};

// Custom comparator for sorting queries in Mo's order
bool compareQueries(const Query &a, const Query &b) {
    int blockSize = sqrt(a.r); // assume the block size by r (could also use l or sqrt(N))
    if (a.l / blockSize != b.l / blockSize)
        return a.l < b.l;
    return (a.l / blockSize % 2 == 0) ? (a.r < b.r) : (a.r > b.r);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    vector<Query> queries;
    for (int i = 0; i < Q; ++i) {
        int l, r;
        cin >> l >> r;
        queries.emplace_back(l - 1, r - 1, i); // Convert 1-based index to 0-based
    }

    // Sort queries based on Mo's algorithm ordering
    sort(queries.begin(), queries.end(), compareQueries);

    vector<int> answer(Q, -1);
    vector<int> freq(N + 1, 0); // Frequency of each element in the current range
    vector<int> candidates; // Stores elements with non-zero frequency in current range

    int currentL = 0, currentR = -1;

    auto add = [&](int pos) {
        int val = A[pos];
        if (++freq[val] == 1) candidates.push_back(val);
    };

    auto remove = [&](int pos) {
        int val = A[pos];
        if (--freq[val] == 0) candidates.erase(remove(candidates.begin(), candidates.end(), val), candidates.end());
    };

    for (const auto& q : queries) {
        int left = q.l;
        int right = q.r;
        int threshold = (right - left + 1) / 3;

        // Extend the range to [left, right]
        while (currentR < right) add(++currentR);
        while (currentR > right) remove(currentR--);
        while (currentL < left) remove(currentL++);
        while (currentL > left) add(--currentL);

        // Check for the smallest element meeting the frequency condition
        int minValue = INT_MAX;
        for (int candidate : candidates) {
            if (freq[candidate] > threshold) {
                minValue = min(minValue, candidate);
            }
        }

        answer[q.idx] = (minValue == INT_MAX) ? -1 : minValue;
    }

    // Output results for each query
    for (int i = 0; i < Q; ++i) {
        cout << answer[i] << '\n';
    }

    return 0;
}