#include <bits/stdc++.h>
char nc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
int rd() {
  int x = 0;
  char c = nc();
  while (!isdigit(c)) c = nc();
  while (isdigit(c)) x = x * 10 + c - '0', c = nc();
  return x;
}
const int N = 1e5 + 3;
struct Quer {
  int l, r, t, id;
} Q[N];
struct Chan {
  int pos, val;
} C[N];
int qcnt, ccnt;
int b[N * 2 + 1], bcnt;
int n, m, a[N], B, belong[N];
bool cmp(const Quer& x, const Quer& y) {
  return belong[x.l] ^ belong[y.l]   ? x.l < y.l
         : belong[x.r] ^ belong[y.r] ? x.r < y.r
                                     : x.t < y.t;
}
namespace Block {
int B, belong[N], lim[N], sum[N], a[N];
void init() {
  B = sqrt(n);
  for (int i = 1; i <= n; ++i) belong[i] = i / B, ++lim[belong[i]];
}
void ins(int x, int v) { sum[belong[x]] += v, a[x] += v; }
int mex() {
  int l = 1;
  while (sum[belong[l]] == lim[belong[l]]) l += lim[belong[l]];
  while (a[l]) ++l;
  return l;
}
}  // namespace Block
int num[N * 2 + 1], book[N], ans[N];
void ins(int x) {
  --book[num[x]];
  if (!book[num[x]]) Block ::ins(num[x], -1);
  ++num[x];
  if (!book[num[x]]) Block ::ins(num[x], 1);
  ++book[num[x]];
}
void del(int x) {
  --book[num[x]];
  if (!book[num[x]]) Block ::ins(num[x], -1);
  --num[x];
  if (!book[num[x]]) Block ::ins(num[x], 1);
  ++book[num[x]];
}
void upd(int x, int t) {
  if (Q[x].l <= C[t].pos && C[t].pos <= Q[x].r) {
    del(a[C[t].pos]);
    ins(C[t].val);
  }
  std ::swap(a[C[t].pos], C[t].val);
}
int main() {
  n = rd(), m = rd();
  B = pow(n, 0.666666);
  if (!B) B = 1;
  for (int i = 1; i <= n; ++i) a[i] = rd(), b[++bcnt] = a[i], belong[i] = i / B;
  while (m--) {
    int op = rd();
    if (op == 1) {
      ++qcnt;
      Q[qcnt].l = rd(), Q[qcnt].r = rd(), Q[qcnt].t = ccnt, Q[qcnt].id = qcnt;
    }
    if (op == 2) {
      ++ccnt;
      C[ccnt].pos = rd(), C[ccnt].val = rd();
      b[++bcnt] = C[ccnt].val;
    }
  }
  std ::sort(b + 1, b + 1 + bcnt);
  bcnt = std ::unique(b + 1, b + 1 + bcnt) - b - 1;
  for (int i = 1; i <= n; ++i)
    a[i] = std ::lower_bound(b + 1, b + 1 + bcnt, a[i]) - b;
  for (int i = 1; i <= ccnt; ++i)
    C[i].val = std ::lower_bound(b + 1, b + 1 + bcnt, C[i].val) - b;
  Block ::init();
  std ::sort(Q + 1, Q + 1 + qcnt, cmp);
  for (int i = 1, l = 1, r = 0, t = 0; i <= qcnt; ++i) {
    while (r < Q[i].r) ins(a[++r]);
    while (r > Q[i].r) del(a[r--]);
    while (l < Q[i].l) del(a[l++]);
    while (l > Q[i].l) ins(a[--l]);
    while (t < Q[i].t) upd(i, ++t);
    while (t > Q[i].t) upd(i, t--);
    ans[Q[i].id] = Block ::mex();
  }
  for (int i = 1; i <= qcnt; ++i) std ::cout << ans[i] << '\n';
  return 0;
}
