#include<bits/stdc++.h>

using namespace std;
#define ll long long int 
const int MAXN = 100005;
const int SQRTN = 320;  
bool ar[200004];
vector<ll>p;
void seive()
{
    ll mxN=200000;
    for(int i=0;i<=mxN;i++)
        ar[i]=true;
    ar[0]=ar[1]=false;
    for(int i=2;i*i<=mxN;i++)
    {
        if(ar[i]==true)
        {
            for(int j=i*i;j<=mxN;j+=i)
            {
                ar[j]=false;
            }
        }
    }
    for(int i=1;i<=mxN;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 threshold;
unordered_map<int, int> countMap;  
set<int> candidates;  

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 add(int position, int threshold) {
    int element = arr[position];
    countMap[element]++;
    if (countMap[element] > threshold) {
        candidates.insert(element);
    }
}

void remove(int position, int threshold) {
    int element = arr[position];
    if (countMap[element] > threshold) {
        candidates.erase(element);
    }
    countMap[element]--;
}



int get_min_valid_candidate(int threshold) {
    for (int candidate : candidates) {
        if (countMap[candidate] > threshold) {
            return candidate;
        }
    }
    return -1;
}


void process_queries(int n, int q) {
    ll 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) add(++R, threshold);
        while (R > r) remove(R--, threshold);

       
        while (L < l) remove(L++, threshold);
        while (L > l) add(--L, threshold);

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

int main() {
    ll n, q;
    cin >> n >> q;
    arr.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    queries.resize(q);
    ans.resize(q, -1);

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

    
    sort(queries.begin(), queries.end(), compare);

   
    process_queries(n, q);

    
    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}