#include<bits/stdc++.h>

using namespace std;
#define ll long long int 

const int MAXN = 200005;
const int SQRTN = 320;  

bool ar[200007];
vector<ll>p;
void seive()
{
    
    for(int i=0;i<=MAXN;i++)
        ar[i]=true;
    ar[0]=ar[1]=false;
    for(int i=2;i*i<=MAXN;i++)
    {
        if(ar[i]==true)
        {
            for(int j=i*i;j<=MAXN;j+=i)
            {
                ar[j]=false;
            }
        }
    }
    for(int i=1;i<=MAXN;i++)
    {
        if(ar[i]==true)
            p.push_back(i);
    }


}




// Mo's Algorithm

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

vector<int> ans;
vector<int> arr;
vector<Query> queries;
int frequency[MAXN]; 
int countMap[MAXN];
int threshold;

bool compare(const Query &a, const Query &b) {
    int block_a = a.l / SQRTN;
    int block_b = b.l / SQRTN;
    if (block_a != block_b)
        return block_a < block_b;
    return (block_a % 2 == 0) ? (a.r < b.r) : (a.r > b.r);
}

void update(int position, int delta) {
    int element = arr[position];
    countMap[element] += delta;
    if (countMap[element] > threshold) {
        frequency[element]++;
    } else if (countMap[element] == threshold) {
        frequency[element]--;
    }
}

int get_min_valid_candidate() {
    int min_candidate = -1;
    for (int i = 0; i < MAXN; i++) {
        if (countMap[i] > threshold) {
            if (min_candidate == -1 || i < min_candidate) {
                min_candidate = i;
            }
        }
    }
    return min_candidate;
}

void process_queries(int n, int q) {
    int L = 0, R = -1;
    for (Query &query : queries) {
        int l = query.l - 1, r = query.r - 1; 

        threshold = (r - l + 1) / 3;

        while (R < r) update(++R, 1);
        while (R > r) update(R--, -1);
        
        while (L < l) update(L++, -1);
        while (L > l) update(--L, 1);

        ans[query.idx] = get_min_valid_candidate();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, q;
    cin >> n >> q;
    arr.resize(n);
    ans.resize(q);

    for (int &val : arr) {
        cin >> val;
    }

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

    sort(queries.begin(), queries.end(), compare);
    process_queries(n, q);

    for (const auto &result : ans) {
        cout << result << "\n";
    }

    return 0;
}