#include <bits/stdc++.h>
using namespace std;
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;
template <typename T>
inline void read(T &x) {
  char ch, t = 0;
  x = 0;
  while (!isdigit(ch = (iS == iT
                            ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                               (iS == iT ? EOF : *iS++))
                            : *iS++)))
    t |= ch == '-';
  while (isdigit(ch))
    x = x * 10 + (ch ^ 48),
    ch = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                      (iS == iT ? EOF : *iS++))
                   : *iS++);
  x = t ? -x : x;
}
inline int read_int() {
  int x;
  return read(x), x;
}
inline long long read_ll() {
  long long x;
  return read(x), x;
}
template <typename T>
inline void chkmin(T &a, T b) {
  a = a < b ? a : b;
}
template <typename T>
inline void chkmax(T &a, T b) {
  a = a > b ? a : b;
}
const int MAXN = 200010;
int sq;
int a[MAXN];
int b[MAXN];
int cnt[MAXN];
int vis[MAXN];
int res[MAXN];
int val[MAXN];
struct Mdf {
  int p, fr, to;
  inline void rd() { p = read_int(), fr = b[p], b[p] = to = read_int(); }
} mdf[MAXN];
struct Qry {
  int l, r, t, id;
  inline void rd(int T, int Id) {
    t = T, id = Id, l = read_int(), r = read_int();
  }
  friend bool operator<(Qry a, Qry b) {
    if (a.t / sq != b.t / sq) return a.t < b.t;
    if (a.l / sq != b.l / sq) return a.l < b.l;
    return a.r < b.r;
  }
} qry[MAXN];
inline void Add(int x) { --vis[cnt[x]], ++cnt[x], ++vis[cnt[x]]; }
inline void Del(int x) { --vis[cnt[x]], --cnt[x], ++vis[cnt[x]]; }
inline void Remove(Mdf x, int L, int R) {
  if (L <= x.p && x.p <= R) Del(x.to), Add(x.fr);
  a[x.p] = x.fr;
}
inline void Insert(Mdf x, int L, int R) {
  if (L <= x.p && x.p <= R) Del(x.fr), Add(x.to);
  a[x.p] = x.to;
}
inline int GetAns() {
  int mex = 1;
  while (vis[mex]) ++mex;
  return mex;
}
int main() {
  int n = read_int(), m = read_int(), Q = 0, M = 0, N = 0;
  sq = pow(n, 0.667);
  for (int i = 1; i <= n; i++) val[++N] = a[i] = b[i] = read_int();
  for (int i = 1; i <= m; i++) {
    int op = read_int();
    if (op == 1)
      ++Q, qry[Q].rd(M, Q);
    else
      ++M, mdf[M].rd(), val[++N] = mdf[M].to;
  }
  sort(val + 1, val + 1 + N), N = unique(val + 1, val + 1 + N) - val - 1;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(val + 1, val + 1 + N, a[i]) - val;
  for (int i = 1; i <= M; i++) {
    mdf[i].fr = lower_bound(val + 1, val + 1 + N, mdf[i].fr) - val;
    mdf[i].to = lower_bound(val + 1, val + 1 + N, mdf[i].to) - val;
  }
  sort(qry + 1, qry + 1 + Q);
  vis[0] = 1e9;
  int L = 1, R = 0, T = 0;
  for (int i = 1; i <= Q; i++) {
    Qry q = qry[i];
    while (T > q.t) Remove(mdf[T--], L, R);
    while (T < q.t) Insert(mdf[++T], L, R);
    while (L > q.l) Add(a[--L]);
    while (R < q.r) Add(a[++R]);
    while (L < q.l) Del(a[L++]);
    while (R > q.r) Del(a[R--]);
    res[qry[i].id] = GetAns();
  }
  for (int i = 1; i <= Q; i++) printf("%d\n", res[i]);
  return 0;
}
