#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
using ll = long long;

const int MX = 500005;
const int B = 600;
int a[MX], freq[MX];
map<int,int> nums[MX], block[MX];
int n, n_blocks;

struct Query {
  int i, l, r, b;

  Query() {}
  Query(int i, int l, int r) : i(i), l(l), r(r) {
    b = l/B;
  }

  bool operator < (const Query& other) {
    if (b == other.b) return ((b & 1) ? (r < other.r) : (r > other.r));
    return (b < other.b);
  }
};

int block_get(int ind) {
  return ind/B;
}

int block_get_start(int b) {
  return (B*b);
}

int block_get_end(int b) {
  return min(n-1, B*(b+1)-1);
}

void include(int i) {
  int& x = a[i];
  int b1, b2;

  b1 = block_get(freq[x]);
  nums[freq[x]][x] -= 1;
  assert(nums[freq[x]][x] >= 0);
  if (nums[freq[x]][x] == 0) nums[freq[x]].erase(x);

  freq[x] += 1;

  b2 = block_get(freq[x]);
  nums[freq[x]][x] += 1;

  if (b1 != b2) {
    block[b1][x] -= 1;
    if (block[b1][x] == 0) block[b1].erase(x);
    block[b2][x] += 1;
  }
}

void exclude(int i) {
  int& x = a[i];
  int b1, b2;

  b1 = block_get(freq[x]);
  nums[freq[x]][x] -= 1;
  assert(nums[freq[x]][x] >= 0);
  if (nums[freq[x]][x] == 0) nums[freq[x]].erase(x);

  freq[x] -= 1;

  b2 = block_get(freq[x]);
  nums[freq[x]][x] += 1;

  if (b1 != b2) {
    block[b1][x] -= 1;
    if (block[b1][x] == 0) block[b1].erase(x);
    block[b2][x] += 1;
  }
}

int query(int l) {
  int i, b, ret;
  b = block_get(l);
  ret = INT_MAX;
  for (i = block_get_end(b); i >= l; --i) {
    if (!nums[i].empty()) ret = min(ret, nums[i].begin()->first);
  }
  for (i = b+1; i < n_blocks; ++i) {
    if (!block[i].empty()) ret = min(ret, block[i].begin()->first);
  }
  if (ret == INT_MAX) ret = -1;
  return ret;
}

int main() {
  FAST;
  memset(freq, 0, sizeof(freq));

  int m, i, l, r, ql, qr, qi, len;
  cin >> n >> m;
  n_blocks = (n+B-1)/B;

  for (i = 0; i < n; ++i) cin >> a[i];
  for (i = 0; i < n; ++i) {
    nums[0][a[i]] += 1;
    block[0][a[i]] += 1;
  }

  vector<Query> q(m);
  vector<int> ans(m);
  for (i = 0; i < m; ++i) {
    cin >> l >> r;
    --l; --r;
    q[i] = Query(i, l, r);
  }
  sort(q.begin(), q.end());

  l = 0; r = -1;
  for (i = 0; i < m; ++i) {
    qi = q[i].i;
    ql = q[i].l;
    qr = q[i].r;

    while (l > ql) include(--l);
    while (r < qr) include(++r);
    while (l < ql) exclude(l++);
    while (r > qr) exclude(r--);

    len = (qr - ql + 1) / 3;
    ans[qi] = query(len+1);
  }

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

  return 0;
}