#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, m, q;
int a[200000];
int used[200000], cnt[200000];
struct node {
  int l, r, num, lk, rk, t;
} b[200000];
struct node2 {
  int num, col;
} c[200000];
struct node3 {
  bool f;
  int v, num;
} d[500000];
inline bool cmp2(node3 x, node3 y) { return x.v < y.v; }
inline bool cmp(node x, node y) {
  if (x.lk == y.lk) {
    if (x.rk == y.rk) return x.t < y.t;
    return x.rk < y.rk;
  }
  return x.lk < y.lk;
}
int la[200000];
int l, r, ans, o = 1, pro, cha, tim, tot;
int main() {
  n = read(), m = 2500, q = read();
  for (register int i = 1; i <= n; ++i)
    d[i].v = read(), d[i].f = 1, d[i].num = i;
  for (register int i = 1; i <= q; ++i) {
    int z;
    int x, y;
    z = read();
    x = read(), y = read();
    if (z == 1) {
      ++pro;
      b[pro].l = x;
      b[pro].r = y;
      b[pro].lk = (b[pro].l - 1) / m + 1;
      b[pro].rk = (b[pro].r - 1) / m + 1;
      b[pro].num = pro;
      b[pro].t = cha;
    } else {
      ++cha;
      c[cha].num = x;
      c[cha].col = y;
      d[n + cha].v = y;
      d[n + cha].f = 0;
      d[n + cha].num = cha;
    }
  }
  sort(d + 1, d + n + cha + 1, cmp2);
  for (int i = 1; i <= n + cha; ++i) {
    if (d[i - 1].v != d[i].v) ++tot;
    if (d[i].f)
      a[d[i].num] = tot;
    else
      c[d[i].num].col = tot;
  }
  sort(b + 1, b + pro + 1, cmp);
  l = b[1].l, r = b[1].l - 1;
  int p = pro;
  while (p--) {
    while (r < b[o].r)
      --cnt[used[a[r + 1]]], ++cnt[used[a[r + 1]] + 1], ans += !used[a[++r]]++;
    while (r > b[o].r)
      --cnt[used[a[r]]], ++cnt[used[a[r]] - 1], ans -= !--used[a[r--]];
    while (l < b[o].l)
      --cnt[used[a[l]]], ++cnt[used[a[l]] - 1], ans -= !--used[a[l++]];
    while (l > b[o].l)
      --cnt[used[a[l - 1]]], ++cnt[used[a[l - 1]] + 1], ans += !used[a[--l]]++;
    while (tim < b[o].t) {
      if (c[++tim].num >= b[o].l && c[tim].num <= b[o].r) {
        int nnn = c[tim].num;
        --cnt[used[a[nnn]]];
        ++cnt[used[a[nnn]] - 1];
        ans -= !--used[a[nnn]];
        swap(a[nnn], c[tim].col);
        --cnt[used[a[nnn]]];
        ++cnt[used[a[nnn]] + 1];
        ans += !used[a[nnn]]++;
      } else
        swap(a[c[tim].num], c[tim].col);
    }
    while (tim > b[o].t) {
      if (c[tim].num >= b[o].l && c[tim].num <= b[o].r) {
        int nnn = c[tim].num;
        --cnt[used[a[nnn]]];
        ++cnt[used[a[nnn]] - 1];
        ans -= !--used[a[nnn]];
        swap(a[nnn], c[tim].col);
        --cnt[used[a[nnn]]];
        ++cnt[used[a[c[tim--].num]] + 1];
        ans += !used[a[nnn]]++;
      } else
        swap(a[c[tim].num], c[tim].col), tim--;
    }
    int c = 0;
    while (cnt[++c])
      ;
    la[b[o].num] = c, ++o;
  }
  for (register int i = 1; i <= pro; i++) printf("%d\n", la[i]);
  return 0;
}
