#include<bits/stdc++.h>

using namespace std;
#define ll long long int 

const int MAXN = 200005;
const int SQRTN = 520;  

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


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


int get_min_valid_candidate(int threshold) {
    int min_candidate = -1;
    for (const auto &entry : countMap) {
        int element = entry.first;
        if (entry.second > threshold && (min_candidate == -1 || element < min_candidate)) {
            min_candidate = element;
        }
    }
    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) 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() {
    
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int 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;
}