#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 50;
int n, m, tpq, tpc, len, a[maxn], tot;
int cnt[maxn], cnt2[maxn], ans[maxn];
struct que {
  int id, l, r, tim;
  bool operator<(que i) const {
    return l / len == i.l / len ? (r / len == i.r / len ? tim < i.tim : r < i.r)
                                : l < i.l;
  }
} q[maxn];
struct cha {
  int pos, col;
} c[maxn];
inline void add(int x) {
  cnt2[cnt[a[x]]]--;
  cnt[a[x]]++;
  cnt2[cnt[a[x]]]++;
}
inline void del(int x) {
  cnt2[cnt[a[x]]]--;
  cnt[a[x]]--;
  cnt2[cnt[a[x]]]++;
}
inline void modify(int id, int x) {
  if (c[x].pos >= q[id].l && c[x].pos <= q[id].r) {
    int tmp = a[c[x].pos];
    del(c[x].pos);
    a[c[x].pos] = c[x].col;
    add(c[x].pos);
    a[c[x].pos] = tmp;
  }
  swap(a[c[x].pos], c[x].col);
}
struct node {
  int id, x, y;
} b[maxn * 2];
int tp;
bool cmp1(node a, node b) { return a.id < b.id; }
bool cmp2(node a, node b) { return a.x < b.x; }
inline int read() {
  register int x = 0, y = 1;
  register char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') y = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  return x * y;
}
int main() {
  n = read();
  m = read();
  len = pow(n, 0.66666);
  for (register int i = 1; i <= n; i++) {
    a[i] = read();
    b[++tp].id = i;
    b[tp].x = b[tp].y = a[i];
  }
  for (register int i = 1; i <= m; i++) {
    register int ch;
    ch = read();
    if (ch == 1) {
      tpq++;
      q[tpq].id = tpq;
      q[tpq].tim = tpc;
      q[tpq].l = read();
      q[tpq].r = read();
    } else {
      tpc++;
      c[tpc].pos = read();
      c[tpc].col = read();
      b[++tp].id = i + n;
      b[tp].x = b[tp].y = c[tpc].col;
    }
  }
  stable_sort(b + 1, b + 1 + tp, cmp2);
  b[1].x = 1;
  for (register int i = 2; i <= tp; i++) {
    if (b[i - 1].y == b[i].y)
      b[i].x = b[i - 1].x;
    else
      b[i].x = b[i - 1].x + 1;
  }
  stable_sort(b + 1, b + 1 + tp, cmp1);
  for (register int i = 1; i <= tp; i++) {
    if (i <= n)
      a[i] = b[i].x;
    else
      c[i - n].col = b[i].x;
  }
  stable_sort(q + 1, q + 1 + tpq);
  int l = 0, r = 0, cur = 0;
  for (register int i = 1; i <= tpq; i++) {
    while (l < q[i].l) {
      del(l);
      l++;
    }
    while (l > q[i].l) {
      add(l - 1);
      l--;
    }
    while (r < q[i].r) {
      add(r + 1);
      r++;
    }
    while (r > q[i].r) {
      del(r);
      r--;
    }
    while (cur < q[i].tim) {
      modify(i, cur + 1);
      cur++;
    }
    while (cur > q[i].tim) {
      modify(i, cur);
      cur--;
    }
    register int res = 0;
    while (cnt2[res + 1] != 0) res++;
    ans[q[i].id] = res + 1;
  }
  for (int i = 1; i <= tpq; i++) printf("%d\n", ans[i]);
  return 0;
}
