median_query

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define fi first
#define se second

#define lsb(x) (x & (-x))

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
#define FILE_NAME "median_query"
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};
InParser fin(FILE_NAME ".in");
ofstream fout(FILE_NAME ".out");
#define endl '\n'
#endif

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

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

int n, m;
int a[NMAX];
Query q[NMAX];
int aib[NMAX];
int ans[NMAX];
int bucket[NMAX];
unordered_map<int, int> val;

void aib_update(int pos, int val) {
    for (int i = pos; i <= n; i += lsb(i))
            aib[i] += val;
}

int aib_query(int pos) {
    int ret = 0;
    for (int i = pos; i >= 1; i -= lsb(i))
        ret += aib[i];
    return ret;
}

void read() {
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    for (int i = 1; i <= m; i++) {
        fin >> q[i].l >> q[i].r;
        q[i].idx = i;
    }
}

void precalc() {
    int bsz = 2 * sqrt(n);
    for (int i = 1; i <= n; i++)
        bucket[i] = (i - 1) / bsz + 1;

    vector<int*> v;
    for (int i = 1; i <= n; i++)
        v.push_back(a + i);

    sort(all(v), [](const int *a, const int *b) {
        return *a < *b;
    });

    val[1] = *v[0];
    *v[0] = 1;
    int mx_val = 1;

    for (int i = 1; i < n; i++) {
        mx_val += *v[i] != *v[i - 1];
        val[mx_val] = *v[i];
        *v[i] = mx_val;
    }
}

bool cmp_mo(const Query &a, const Query &b) {
    if (bucket[a.l] == bucket[b.l]) return a.r < b.r;
    return a.l < b.l;
}

int bs(int len) {
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (2 * aib_query(mid) < len)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return r + 1;
}

void solve() {
    sort(q + 1, q + m + 1, cmp_mo);

    int l = 1, r = 1;
    aib_update(a[1], 1);

    for (int i = 1; i <= m; i++) {
        int ql = q[i].l, qr = q[i].r;

        while (l < ql) aib_update(a[l++], -1);
        while (qr < r) aib_update(a[r--], -1);
        while (ql < l) aib_update(a[--l], 1);
        while (r < qr) aib_update(a[++r], 1);

        ans[q[i].idx] = val[bs(r - l + 1)];
    }

    for (int i = 1; i <= m; i++)
        fout << ans[i] << endl;
}

int main() {
    read();
    precalc();
    solve();
    return 0;
}