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

const int N = 2e5+2, B = 440;
int a[N];
set<pair<int,int>,greater<pair<int,int>>> st;
unordered_map<int,int> mp;
void remove(int idx) {
    if(st.find({mp[a[idx]],a[idx]}) != st.end()) st.erase({mp[a[idx]],a[idx]});
    mp[a[idx]]--;
    if(mp[a[idx]]) st.insert({mp[a[idx]],a[idx]});
}
void add(int idx) {
    if(st.find({mp[a[idx]],a[idx]}) != st.end()) st.erase({mp[a[idx]],a[idx]});
    mp[a[idx]]++;
    st.insert({mp[a[idx]],a[idx]});
}
int get_answer(int l) {
    if(st.empty()) return -1;
    auto it = st.begin();
    int ans = INT_MAX;
    if((*it).first > l) ans = min(ans, (*it).second);
    st.erase(st.begin());
    if(st.size()) {
        auto it1 = st.begin();
        if((*it1).first > l) ans = min(ans, (*it1).second);
    }
    st.insert({(*it).first,(*it).second});
    if(ans == INT_MAX) return -1;
    return ans;
}


struct Query {
  int l, r, idx;
  bool operator < (const Query &x) const {
    if(l / B == x.l / B) return ((l / B) & 1) ? r > x.r : r < x.r;
    return l / B < x.l / B;
  }
};

vector<int> mo_s_algorithm(vector<Query> queries) {
    vector<int> answers(queries.size());
    sort(queries.begin(), queries.end());

    int cur_l = 0;
    int cur_r = -1;
    for (Query q : queries) {
        while (cur_l > q.l) {
            cur_l--;
            add(cur_l);
        }
        while (cur_r < q.r) {
            cur_r++;
            add(cur_r);
        }
        while (cur_l < q.l) {
            remove(cur_l);
            cur_l++;
        }
        while (cur_r > q.r) {
            remove(cur_r);
            cur_r--;
        }
        answers[q.idx] = get_answer((q.r - q.l + 1) / 3);
    }
    return answers;
}

void solve() {
    int n,q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<Query> query(q);
    for(int i = 0; i < q; i++) {
        cin >> query[i].l >> query[i].r;
        query[i].idx = i;
    }
    vector<int> ans = mo_s_algorithm(query);
    for(int i = 0; i < q; i++)
        cout << ans[i] << '\n';
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    // cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}