#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

struct Q {
    int l, r, idx;
};

bool cmp(const Q& a, const Q& b) {
    int b_size = 1000;
    if (a.l / b_size != b.l / b_size) {
        return a.l < b.l;
    }
    return a.r < b.r;
}

vector<int> mo(int n, int q, const vector<int>& a, const vector<Q>& qry) {
    vector<int> res(q);
    vector<int> f(n + 1, 0);
    int cl = 0, cr = 0;

    for (int i = 0; i < q; ++i) {
        int l = qry[i].l - 1;
        int r = qry[i].r - 1;

        while (cr <= r) {
            f[a[cr]]++;
            cr++;
        }
        while (cr > r + 1) {
            cr--;
            f[a[cr]]--;
        }

        while (cl < l) {
            f[a[cl]]--;
            cl++;
        }
        while (cl > l) {
            cl--;
            f[a[cl]]++;
        }

        int t = (r - l + 1) / 3;
        int mX = numeric_limits<int>::max();

        for (int j = 1; j <= n; ++j) {
            if (f[j] > t) {
                mX = min(mX, j);
            }
        }

        res[qry[i].idx] = (mX == numeric_limits<int>::max()) ? -1 : mX;
    }

    return res;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<Q> qry(q);
    for (int i = 0; i < q; ++i) {
        cin >> qry[i].l >> qry[i].r;
        qry[i].idx = i;
    }

    sort(qry.begin(), qry.end(), cmp);
    vector<int> res = mo(n, q, a, qry);

    for (int r : res) {
        cout << r << endl;
    }

    return 0;
}