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

// A node holds up to two (value, count) pairs for the BM k=3 algorithm
struct Node {
    // pairs: (candidate value, counter)
    pair<int,int> a, b;
    Node(pair<int,int> _a={0,0}, pair<int,int> _b={0,0}) : a(_a), b(_b) {}
};

// Merge two BM-k=3 nodes, keeping at most two candidates
Node mergeNode(const Node &L, const Node &R) {
    vector<pair<int,int>> C;
    if (L.a.second) C.push_back(L.a);
    if (L.b.second) C.push_back(L.b);
    if (R.a.second) C.push_back(R.a);
    if (R.b.second) C.push_back(R.b);

    // consolidate duplicates
    sort(C.begin(), C.end(), [](auto &x, auto &y){ return x.first < y.first; });
    vector<pair<int,int>> D;
    for (auto &p : C) {
        if (!D.empty() && D.back().first == p.first) {
            D.back().second += p.second;
        } else {
            D.push_back(p);
        }
    }

    // reduce until at most 2 remain
    while ((int)D.size() > 2) {
        int mn = min_element(D.begin(), D.end(),
                             [](auto &x, auto &y){ return x.second < y.second; })->second;
        vector<pair<int,int>> E;
        for (auto &p : D) {
            int cnt = p.second - mn;
            if (cnt > 0) E.emplace_back(p.first, cnt);
        }
        D.swap(E);
    }

    // pad with zeros if needed
    pair<int,int> A = D.size()>0 ? D[0] : make_pair(0,0);
    pair<int,int> B = D.size()>1 ? D[1] : make_pair(0,0);
    return Node(A,B);
}

struct SegTree {
    int n;
    vector<Node> st;
    SegTree(const vector<int> &A) {
        n = A.size();
        st.resize(4*n);
        build(1, 0, n-1, A);
    }
    void build(int p, int l, int r, const vector<int> &A) {
        if (l == r) {
            st[p] = Node({A[l],1}, {0,0});
            return;
        }
        int m = (l+r)/2;
        build(p<<1, l, m, A);
        build(p<<1|1, m+1, r, A);
        st[p] = mergeNode(st[p<<1], st[p<<1|1]);
    }
    Node query(int p, int l, int r, int i, int j) {
        if (r < i || l > j) return Node({0,0},{0,0});
        if (l >= i && r <= j) return st[p];
        int m = (l+r)/2;
        Node L = query(p<<1, l, m, i, j);
        Node R = query(p<<1|1, m+1, r, i, j);
        return mergeNode(L,R);
    }
    // user‐facing:
    Node query(int i, int j) { return query(1,0,n-1,i,j); }
};

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

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

    // build position lists
    vector<vector<int>> pos(N+1);
    for(int i=0;i<N;i++){
        pos[A[i]].push_back(i);
    }

    // build segment tree
    SegTree st(A);

    while(Q--){
        int l, r;
        cin >> l >> r;
        --l; --r;  // to 0-based

        // get up to 2 candidates
        Node nd = st.query(l, r);
        vector<int> candidates;
        if (nd.a.second) candidates.push_back(nd.a.first);
        if (nd.b.second) candidates.push_back(nd.b.first);

        int ans = INT_MAX;
        int threshold = (r - l + 1) / 3;
        for (int x : candidates) {
            // count occurrences via binary search
            auto &V = pos[x];
            int cnt = int(upper_bound(V.begin(), V.end(), r)
                          - lower_bound(V.begin(), V.end(), l));
            if (cnt > threshold) {
                ans = min(ans, x);
            }
        }
        cout << (ans==INT_MAX ? -1 : ans) << "\n";
    }
    return 0;
}