#include <bits/stdc++.h>
using namespace std;
struct Qu {
  int tp, lp, l, r, t, idx;
  bool operator<(Qu d) const {
    if (tp != d.tp) return tp < d.tp;
    if (lp != d.lp) return lp < d.lp;
    return r < d.r;
  };
} qu[100005];
struct Change {
  int idx, px, x;
} change[100005];
int arr[100005], ans[100005], chk[100005], cnt[2 * 100005];
int n, cn, qn;
int L, R, T;
int C;
map<int, int> num;
int uni(int x) { return num.count(x) ? num[x] : num[x] = C++; }
void add(int x) {
  chk[cnt[x]]--;
  chk[++cnt[x]]++;
}
void del(int x) {
  chk[cnt[x]]--;
  chk[--cnt[x]]++;
}
void change_arr(int idx, int x) {
  if (idx >= L && idx <= R) {
    add(x);
    del(arr[idx]);
  }
  arr[idx] = x;
}
int get(int l, int r, int t) {
  int i;
  while (T < t) {
    T++;
    change_arr(change[T].idx, change[T].x);
  }
  while (T > t) {
    change_arr(change[T].idx, change[T].px);
    T--;
  }
  for (i = L; i <= R; i++) {
    if (i >= l && i <= r) {
      i = r;
      continue;
    }
    del(arr[i]);
  }
  for (i = l; i <= r; i++) {
    if (i >= L && i <= R) {
      i = R;
      continue;
    }
    add(arr[i]);
  }
  L = l;
  R = r;
  for (i = 1; chk[i]; i++)
    ;
  return i;
}
int main() {
  int i, p, tp, l, r, q, x;
  scanf("%d %d", &n, &q);
  for (i = 1; i <= n; i++) {
    scanf("%d", &x);
    arr[i] = uni(x);
  }
  p = pow((double)n, 0.666);
  while (q--) {
    scanf("%d %d %d", &tp, &l, &r);
    if (tp == 1)
      qu[qn] = {cn / p, l / p, l, r, cn, qn}, qn++;
    else
      cn++, change[cn] = {l, -1, uni(r)};
  }
  for (i = 1; i <= cn; i++) {
    change[i].px = arr[change[i].idx];
    arr[change[i].idx] = change[i].x;
  }
  L = 0;
  R = -1;
  sort(qu, qu + qn);
  T = cn;
  for (i = 0; i < qn; i++) ans[qu[i].idx] = get(qu[i].l, qu[i].r, qu[i].t);
  for (i = 0; i < qn; i++) printf("%d\n", ans[i]);
  return 0;
}
