代码：

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 2e5 + 5, kMaxM = 2e5 + 5, kMaxA = 2e5 + 5, kMaxB = sqrt(kMaxA) + 100;

int n, m, maxi, b1, b2, cnt; // b1 : 下标, b2 : 值域 
int l, r;
int res[kMaxM], lt[kMaxB], rt[kMaxB], a[kMaxN], c[kMaxA], bel[kMaxA], tot[kMaxB];

struct Q {
  int l, r, sl, id;
  
  Q() {}
  Q(int _l, int _r, int _id) {
    l = _l, r = _r, sl = l / b1, id = _id;
  }
  
  friend bool operator < (const Q& q1, const Q& q2) {
    if (q1.sl != q2.sl) {
      return q1.l < q2.l;
    }
    else {
      if (q1.sl & 1) {
        return q1.r < q2.r;
      }
      else {
        return q1.r > q2.r;
      }
    }
  }
} q[kMaxM] ;

void add(int x) {
  if (++c[x] == 1) {
    ++tot[bel[x]];
  }
}
void del(int x) {
  if (--c[x] == 0) {
    --tot[bel[x]];
  }
}
int query() {
  for (int i = 1; i <= cnt; ++i) {
    if (tot[i] == rt[i] - lt[i] + 1) {
      continue ;
    }
    for (int j = lt[i]; j <= rt[i]; ++j) {
      if (!c[j]) {
        return j;
      }
    }
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    maxi = max(maxi, a[i]);
  }
  b1 = sqrt(n), b2 = sqrt(maxi);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &l, &r);
    q[i] = Q(l, r, i);
  }
  sort(q + 1, q + 1 + m);
  for (int i = 0; i <= maxi; ++i) {
    if (i % b2 == 0) {
      ++cnt;
      lt[cnt] = i, rt[cnt] = min(cnt * b2 - 1, maxi);
    }
    bel[i] = cnt;
  }
  l = 1, r = 0;
  for (int i = 1; i <= m; ++i) {
    int ql = q[i].l, qr = q[i].r;
    while (l < ql) del(a[l++]);
    while (l > ql) add(a[--l]);
    while (r < qr) add(a[++r]);
    while (r > qr) del(a[r--]);
    res[q[i].id] = query();
  }
  for (int i = 1; i <= m; ++i) {
    printf("%d\n", res[i]);
  }
  return 0;
}