#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
#define all(x) x.begin(), x.end()

const int INF = 1e9;
const int N = 1e5+5;

struct query{
    int l, r, id;
} Q[N];
int n, q, a[N], BLOCK_SIZE, L=1, R=0, cnt[N], res[N];
set<int> se;

void solve(int i){
    while (R<Q[i].r){
        R++;
        if (cnt[a[R]]==0){
            se.erase(a[R]);
        }
        cnt[a[R]]++;
    }
    while (L>Q[i].l){
        L--;
        if (cnt[a[L]]==0){
            se.erase(a[L]);
        }
        cnt[a[L]]++;
    }
    while (R>Q[i].r){
        cnt[a[R]]--;
        if (cnt[a[R]]==0){
            se.insert(a[R]);
        }
        R--;
    }
    while (L<Q[i].l){
        cnt[a[L]]--;
        if (cnt[a[L]]==0){
            se.insert(a[L]);
        }
        L++;
    }
}

bool MO(query x, query y){
    int X = x.l/BLOCK_SIZE;
    int Y = y.l/BLOCK_SIZE;

    if (X!=Y) return X<Y;
    if (X&1) return x.r<y.r;
    return x.r>y.r;
}

int main(){
    fastIO;

    cin >> n >> q;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=q; i++){
        cin >> Q[i].l >> Q[i].r;
        Q[i].id = i;
    }
    BLOCK_SIZE = sqrt(n);
    sort(Q+1, Q+1+q, MO);
    for (int i=1; i<=n; i++) se.insert(i);
    for (int i=1; i<=q; i++){
        solve(i);
        res[Q[i].id] = *(se.begin());
    }
    for (int i=1; i<=q; i++){
        cout << res[i] << '\n';
    }
}