#include <bits/stdc++.h>
using namespace std;
struct opt {
  int t;
  int l;
  int r;
  int p;
  int id;
  int ans;
};
const int MAXN = 2e5 + 100;
int n, q, len;
int a[MAXN], cnt[MAXN], sz[2 * MAXN];
vector<int> b;
vector<opt> c, d;
void modify(int x, bool e) {
  --x;
  int l = a[d[x].l], r = d[x].r;
  if (e) {
    --sz[cnt[l]--];
    ++sz[cnt[l]];
    --sz[cnt[r]++];
    ++sz[cnt[r]];
  }
  swap(a[d[x].l], d[x].r);
}
void inc(int x) {
  --sz[cnt[a[x]]++];
  ++sz[cnt[a[x]]];
}
void dec(int x) {
  --sz[cnt[a[x]]--];
  ++sz[cnt[a[x]]];
}
int query() {
  int up = 2 * sqrt(n);
  for (int i = 1; i < up + 1; ++i) {
    if (sz[i + 100000] == 0) return i;
  }
}
int search(int x) {
  int l = 0, r = b.size() - 1;
  while (l < r) {
    int mid = (l + r + 1) / 2;
    if (b[mid] <= x)
      l = mid;
    else
      r = mid - 1;
  }
  return l;
}
bool cmp(const opt &x, const opt &y) {
  if (x.p / len != y.p / len)
    return x.p < y.p;
  else {
    if (x.l / len != y.l / len)
      return x.l < y.l;
    else
      return x.r < y.r;
  }
}
bool cmp2(const opt &x, const opt &y) { return x.id < y.id; }
int read() {
  int x;
  scanf("%d", &x);
  return x;
}
int main() {
  b.reserve(210000);
  n = read();
  q = read();
  for (int i = 1; i < n + 1; ++i) {
    a[i] = read();
    b.push_back(a[i]);
  }
  int o = 0;
  for (int i = 0; i < q; ++i) {
    opt t;
    t.t = read();
    t.l = read();
    t.r = read();
    t.p = d.size();
    t.id = i;
    if (t.t == 2) {
      b.push_back(t.r);
      d.push_back(t);
    } else
      c.push_back(t);
  }
  sort(b.begin(), b.end());
  auto it = unique(b.begin(), b.end());
  b.erase(it, b.end());
  for (int i = 1; i < n + 1; ++i) a[i] = search(a[i]);
  for (auto &i : d) i.r = search(i.r);
  for (int i = 0; i < b.size() + 1; ++i) cnt[i] = 100000;
  len = pow(n, 2.0 / 3.0);
  sort(c.begin(), c.end(), cmp);
  int l = 1, r = 0, h = 0;
  for (auto &i : c) {
    while (l > i.l) {
      --l;
      inc(l);
    }
    while (r < i.r) {
      ++r;
      inc(r);
    }
    while (l < i.l) {
      dec(l);
      ++l;
    }
    while (r > i.r) {
      dec(r);
      --r;
    }
    while (h < i.p) {
      ++h;
      modify(h, d[h - 1].l >= l && d[h - 1].l <= r);
    }
    while (h > i.p) {
      modify(h, d[h - 1].l >= l && d[h - 1].l <= r);
      --h;
    }
    i.ans = query();
  }
  sort(c.begin(), c.end(), cmp2);
  for (auto i : c) {
    printf("%d\n", i.ans);
  }
  return 0;
}
