SQRTT

#include <bits/stdc++.h>
#define MAX 100007
#define SQ 327
#define  mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int bucket[MAX], freq[SQ][MAX];
pii interval[SQ][SQ];
int ini[MAX], fim[MAX], a[MAX], n;

int actual[MAX];
struct SQRTT {

    void build(){
        memset(ini, -1, sizeof ini);
        memset(fim, -1, sizeof fim);
        // Delimitando intervalos dos buckets
        bucket[0] = 0; ini[0] = 0;
        for(int i = 1; i < n; i++){
            bucket[i] = i/SQ;
            ini[bucket[i]] = (bucket[i] != bucket[i-1])? i: ini[bucket[i]];
            fim[bucket[i-1]] = (bucket[i] != bucket[i-1])? i-1: fim[bucket[i-1]];
        }
        fim[bucket[n-1]] = n-1;

        // Acumulando
        for(int i = 0; i < n; i++) freq[bucket[i]][a[i]]++;

        for(int i = 1; i < SQ && ini[i] != -1; i++){
            for(int j = 0; j < n; j++) freq[i][j] += freq[i-1][j];
        }

        // pegando a melhor resposta entre os buckets
        for(int i = 0; i < SQ && ini[i] != -1; i++){
            memset(actual, 0, sizeof actual);
            int best = a[ini[i]];
            for(int j = ini[i]; j < n; j++){
                actual[a[j]]++;
                if(actual[a[j]] > actual[best]) best = a[j];

                if(fim[bucket[j]] == j) {interval[i][bucket[j]].first = best; interval[i][bucket[j]].second = actual[best];}
            }
        }
        memset(actual, 0, sizeof actual);
    }

    int query(int l, int r){
        int bl = bucket[l], br = bucket[r];
        if(bl == br){
            int best = l;
            for(int i = l; i <= r; i++){
                actual[a[i]]++;
                if(actual[a[i]] > actual[best]) best = a[i];
            }

            // limpando
            for(int i = l; i <= r; i++) actual[a[i]]--;
            return best;
        }

        bl++; br--;
        pii best;
        if(bl <= br) best = interval[bl][br];
        else best = mp(-1, -1);
        bl--; br++;

        for(int i = l; i <= fim[bl]; i++) actual[a[i]]++;
        for(int i = ini[br]; i <= r; i++) actual[a[i]]++;

        for(int i = l; i <= fim[bl]; i++) {
            int total = freq[br-1][a[i]];
            total -= freq[bl][a[i]];

            total = (total < 0)? actual[a[i]]: total + actual[a[i]];
            best.first = (total > best.second)? a[i]: best.first;
            best.second = (total > best.second)? total: best.second;
        }
        for(int i = ini[br]; i <= r; i++) {
            int total = freq[br-1][a[i]];
            total -= freq[bl][a[i]];

            total = (total < 0)? actual[a[i]]: total + actual[a[i]];
            best.first = (total > best.second)? a[i]: best.first;
            best.second = (total > best.second)? total: best.second;
        }

        // limpando
        for(int i = l; i <= fim[bl]; i++) actual[a[i]]--;
        for(int i = ini[br]; i <= r; i++) actual[a[i]]--;
        return best.first;
    }
};

int main(){
    SQRTT ds;
    int m; scanf("%d %d", &n, &m);

    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    ds.build();
    while((m--)){
        int l, r; scanf("%d %d", &l, &r);
        printf("%d\n", ds.query(l, r));
    }

    return 0;
}