#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T& x) {
  bool fu = 0;
  char c;
  for (c = getchar(); c <= 32; c = getchar())
    ;
  if (c == '-') fu = 1, c = getchar();
  for (x = 0; c > 32; c = getchar()) x = x * 10 + c - '0';
  if (fu) x = -x;
};
template <class T>
inline void read(T& x, T& y) {
  read(x);
  read(y);
}
template <class T>
inline void read(T& x, T& y, T& z) {
  read(x);
  read(y);
  read(z);
}
const int N = 200010, G = 200;
int n, m, i, j, k, l, p, z, t, x, y, res, ci;
int q0[N], q1[N], q2[N], a[N], o[N], d[N], g, w[N], c1[N], c2[N];
vector<int> v[N], cc[N];
int op[N], ct[N], li[N];
int cnt(int s, int x) {
  return upper_bound(v[s].begin(), v[s].end(), x) - v[s].begin();
}
void reb() {
  for (i = 1; i <= g; i++) a[w[i]] = c2[i];
  g = 0;
  for (i = 1; i <= o[0]; i++) v[i].clear();
  for (i = 1; i <= n; i++) cc[i].clear();
  for (i = 1; i <= n; i++) {
    v[a[i]].push_back(i);
    cc[v[a[i]].size()].push_back(i);
  }
}
void st(int i) {
  op[i] = z;
  ct[i] = cnt(i, x);
  li[++li[0]] = i;
  if (v[i].size() >= res && v[i][res - 1] <= x) ci--;
}
int main() {
  read(n);
  for (i = 1; i <= n; i++) read(a[i]), o[++o[0]] = a[i];
  read(m);
  for (i = 1; i <= m; i++) {
    read(q0[i], q1[i], q2[i]);
    if (q0[i] == 1) o[++o[0]] = q1[i];
  }
  sort(o + 1, o + 1 + o[0]);
  j = 1;
  for (i = 2; i <= o[0]; i++)
    if (o[i] != o[i - 1]) o[++j] = o[i];
  o[0] = j;
  for (i = 1; i <= n; i++) a[i] = lower_bound(o + 1, o + 1 + o[0], a[i]) - o;
  for (i = 1; i <= m; i++)
    if (q0[i] == 1) q1[i] = lower_bound(o + 1, o + 1 + o[0], q1[i]) - o;
  reb();
  for (z = 1; z <= m; z++) {
    t = q0[z];
    x = q1[z];
    y = q2[z];
    if (t == 1) {
      if (a[y] != x) {
        ++g;
        w[g] = y;
        c1[g] = a[y];
        c2[g] = x;
        a[y] = x;
        if (g >= G) reb();
      }
    } else {
      swap(x, y);
      if (y > 1) y = (y & 1) ? 3 : 2;
      if (y == 1)
        printf("%d\n", o[a[x]]);
      else {
        res = cnt(a[x], x);
        for (i = 1; i <= g; i++)
          if (w[i] <= x)
            if (c1[i] == a[x])
              res--;
            else if (c2[i] == a[x])
              res++;
        if (y == 2)
          printf("%d\n", res);
        else {
          ci = upper_bound(cc[res].begin(), cc[res].end(), x) - cc[res].begin();
          li[0] = 0;
          for (i = 1; i <= g; i++) {
            if (op[c1[i]] != z) st(c1[i]);
            if (op[c2[i]] != z) st(c2[i]);
            if (w[i] <= x) ct[c1[i]]--, ct[c2[i]]++;
          }
          for (i = 1; i <= li[0]; i++)
            if (ct[li[i]] >= res) ci++;
          printf("%d\n", ci);
        }
      }
    }
  }
  return 0;
}
