#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) {
    static int blockSize = sqrt(2 * 1e5); // √(max 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
    unordered_map<int, int> candidateCount; // Maps value to how many times it appears in the current range
    int currentL = 0, currentR = -1;

    auto add = [&](int pos) {
        int val = A[pos];
        freq[val]++;
        candidateCount[val]++;
    };

    auto remove = [&](int pos) {
        int val = A[pos];
        freq[val]--;
        if (freq[val] == 0) {
            candidateCount.erase(val);
        } else {
            candidateCount[val]--;
        }
    };

    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 (const auto& [value, count] : candidateCount) {
            if (count > threshold) {
                minValue = min(minValue, value);
            }
        }

        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;
}