#include <bits/stdc++.h>
const int N = 200005;
int n, qt, a[N], opt, x, y, cnt, Q, ans[N], block, c[N], ct[N], d[N], tot;
struct qry {
  int l, r, p, id;
} q[N];
struct note {
  int x, y, lst;
} b[N];
bool cmp(qry x, qry y) {
  if (x.l / block != y.l / block) return x.l / block < y.l / block;
  if (x.r / block != y.r / block) return x.r / block < y.r / block;
  return x.p < y.p;
}
void del(int x) {
  int t = a[x];
  c[ct[t]]--;
  ct[t]--;
  c[ct[t]]++;
}
void ins(int x) {
  int t = a[x];
  c[ct[t]]--;
  ct[t]++;
  c[ct[t]]++;
}
int main() {
  scanf("%d%d", &n, &qt);
  block = (int)std::pow(n, 2 * 1.0 / 3) + 1;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), d[++tot] = a[i];
  for (int i = 1; i <= qt; i++) {
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 1)
      q[++Q] = {x, y, cnt, Q};
    else
      b[++cnt] = {x, y, 0}, d[++tot] = y;
  }
  std::sort(d + 1, d + tot + 1);
  tot = std::unique(d + 1, d + tot + 1) - d - 1;
  for (int i = 1; i <= n; i++)
    a[i] = std::lower_bound(d + 1, d + tot + 1, a[i]) - d;
  for (int i = 1; i <= cnt; i++)
    b[i].y = std::lower_bound(d + 1, d + tot + 1, b[i].y) - d;
  std::sort(q + 1, q + Q + 1, cmp);
  int pl = 0, pr = 0, p = 0;
  for (int i = 1; i <= Q; i++) {
    qry t = q[i];
    while (p < t.p) {
      p++;
      int x = b[p].x;
      if (x >= pl && x <= pr) del(x);
      b[p].lst = a[x], a[x] = b[p].y;
      if (x >= pl && x <= pr) ins(x);
    }
    while (p > t.p) {
      int x = b[p].x;
      if (x >= pl && x <= pr) del(x);
      a[x] = b[p].lst;
      if (x >= pl && x <= pr) ins(x);
      p--;
    }
    while (pl < t.l) del(pl++);
    while (pl > t.l) ins(--pl);
    while (pr > t.r) del(pr--);
    while (pr < t.r) ins(++pr);
    int lim = (int)sqrt(2 * (t.r - t.l + 1)) + 1;
    for (int j = 1; j <= lim; j++)
      if (!c[j]) {
        ans[t.id] = j;
        break;
      }
  }
  for (int i = 1; i <= Q; i++) printf("%d ", ans[i]);
}
