#include <bits/stdc++.h>
using namespace std;
const int LL = 1 << 19;
char ibuf[LL], *ie = ibuf + LL, *ip = ie - 1;
inline char nc(void) {
  if (++ip == ie)
    if (fread(ip = ibuf, 1, LL, stdin))
      ;
  return *ip;
}
inline int read(void) {
  char opt;
  int flag = 1, res = 0;
  while ((opt = nc()) < '0')
    if (opt == '-') flag = -1;
  while (opt >= '0') {
    res = (res << 3) + (res << 1) + opt - '0';
    opt = nc();
  }
  return res * flag;
}
int a[200001], belong[200001], n, m, qtot, stot, ans, Ans[200001], sum[200001],
    sz, ss[200001], tot, mxx, t[200001];
inline char gc(void) {
  char opt = nc();
  while (opt != 'Q' && opt != 'R') opt = nc();
  return opt;
}
struct Que {
  int l, r, time, pos;
  inline char operator<(Que a) const {
    if (belong[l] == belong[a.l])
      return belong[r] == belong[a.r]
                 ? (((belong[r] ^ belong[l]) & 1) ? time < a.time
                                                  : time > a.time)
             : (belong[l] & 1) ? r < a.r
                               : r > a.r;
    else {
      return l < a.l;
    }
  }
} q[200001];
struct Cmd {
  int v, x, y;
} s[200001];
inline void Add(int x, int v) {
  --ss[sum[x]];
  ++ss[sum[x] += v];
}
inline void Read(void) {
  int i, x, y;
  char opt;
  tot = n = read();
  m = read();
  for (i = 1; i <= n; ++i) mxx = max(mxx, t[i] = a[i] = read());
  for (i = 1; i <= m; ++i) {
    opt = read(), x = read(), t[++tot] = y = read();
    if (opt == 1)
      q[++qtot] = {x, y, stot, qtot};
    else
      s[++stot] = {x, y, a[x]}, a[x] = y;
  }
  sort(t + 1, t + tot + 1);
  tot = unique(t + 1, t + tot + 1) - t - 1;
  for (i = 1; i <= n; ++i) a[i] = lower_bound(t + 1, t + tot + 1, a[i]) - t;
  for (i = 1; i <= stot; ++i) {
    s[i].x = lower_bound(t + 1, t + tot + 1, s[i].x) - t;
    s[i].y = lower_bound(t + 1, t + tot + 1, s[i].y) - t;
  }
  sz = pow(n, 2. / 3);
  for (i = 1; i <= n; ++i) belong[i] = (i - 1) / sz + 1;
  sort(q + 1, q + qtot + 1);
}
inline void Solve(void) {
  int i, j, l = 1, r = 0, now;
  for (i = 1, l = 1, r = 0, now = stot; i <= qtot; ++i) {
    while (r < q[i].r) Add(a[++r], 1);
    while (r > q[i].r) Add(a[r--], -1);
    while (l < q[i].l) Add(a[l++], -1);
    while (l > q[i].l) Add(a[--l], 1);
    while (now < q[i].time) {
      ++now;
      if (l <= s[now].v && s[now].v <= r) {
        Add(a[s[now].v], -1);
        a[s[now].v] = s[now].x;
        Add(a[s[now].v], 1);
      } else
        a[s[now].v] = s[now].x;
    }
    while (now > q[i].time) {
      if (l <= s[now].v && s[now].v <= r) {
        Add(a[s[now].v], -1);
        a[s[now].v] = s[now].y;
        Add(a[s[now].v], 1);
      } else
        a[s[now].v] = s[now].y;
      --now;
    }
    for (j = 1; j <= n; ++j)
      if (!ss[j]) {
        Ans[q[i].pos] = j;
        break;
      }
  }
  for (i = 1; i <= qtot; ++i) printf("%d\n", Ans[i]);
}
int main(void) {
  Read();
  Solve();
  return 0;
}
