#include <bits/stdc++.h>
using namespace std;
set<int> Q;
set<int>::iterator it;
int q[210000 * 2], rec[210000][3], a[210000], n, m, T;
int Sum[210000 * 2], sum[305][210000], bel[210000], cnt[305][500];
int bin(int k) {
  int l = 1, r = q[0];
  while (l < r) {
    int mid = (l + r) / 2;
    if (k <= q[mid])
      r = mid;
    else
      l = mid + 1;
  }
  return l;
}
int main() {
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) scanf("%d", &a[i]), q[++q[0]] = a[i];
  scanf("%d", &T);
  for (int i = 1; i <= T; i++) {
    scanf("%d%d%d", &rec[i][0], &rec[i][1], &rec[i][2]);
    if (rec[i][0] == 1) swap(rec[i][1], rec[i][2]), q[++q[0]] = rec[i][2];
  }
  sort(q + 1, q + q[0] + 1);
  int t = q[0];
  q[0] = 1;
  for (int i = 2; i <= t; i++)
    if (q[i] != q[q[0]]) q[++q[0]] = q[i];
  for (int i = 1; i <= m; i++) a[i] = bin(a[i]);
  for (int i = 1; i <= T; i++)
    if (rec[i][0] == 1) rec[i][2] = bin(rec[i][2]);
  int dd = (int)sqrt(m) + 1;
  int siz = max((int)sqrt(m) + 1, m / 300);
  int L = (m - 1) / siz + 1;
  for (int i = 1; i <= m; i++) bel[i] = (i - 1) / siz + 1;
  for (int i = 1; i <= m; i++) sum[bel[i]][a[i]]++;
  for (int i = 1; i <= q[0]; i++)
    for (int j = 1; j <= L; j++) {
      sum[j][i] += sum[j - 1][i];
      if (sum[j][i] <= dd) cnt[j][sum[j][i]]++;
    }
  for (int i = 1; i <= q[0]; i++)
    if (sum[L][i] > dd) Q.insert(i);
  int cc = 0;
  while (T--) {
    ++cc;
    int kk = rec[cc][0], x = rec[cc][1], y = rec[cc][2];
    if (kk != 1) {
      if (x == 1)
        printf("%d\n", q[a[y]]);
      else if (x % 2 == 0) {
        int t = (y - 1) / siz + 1, t2 = a[y];
        int ans = sum[t - 1][a[y]];
        while (bel[y] == t) {
          ans += a[y] == t2;
          --y;
        }
        printf("%d\n", ans);
      } else {
        int t = (y - 1) / siz + 1;
        for (int i = y; bel[i] == t; i--) Sum[a[i]]++;
        int lim = sum[t - 1][a[y]] + Sum[a[y]], ans = 0;
        for (int i = lim; i <= dd; i++) ans += cnt[t - 1][i];
        for (int i = y; bel[i] == t; i--) {
          ans = ans - (sum[t - 1][a[i]] >= lim) +
                ((sum[t - 1][a[i]] + Sum[a[i]]) >= lim);
          Sum[a[i]] = 0;
        }
        for (it = Q.begin(); it != Q.end(); ++it) {
          int z = *it;
          if (Sum[z] == 0 && sum[t - 1][z] > dd && sum[t - 1][z] >= lim) ++ans;
        }
        printf("%d\n", ans);
      }
    } else {
      int t = (x - 1) / siz + 1;
      for (int i = t; i <= L; i++) {
        if (sum[i][a[x]] <= dd) cnt[i][sum[i][a[x]]]--;
        sum[i][a[x]]--;
        if (sum[i][a[x]] <= dd) cnt[i][sum[i][a[x]]]++;
      }
      if (sum[L][a[x]] == dd) Q.erase(a[x]);
      a[x] = y;
      for (int i = t; i <= L; i++) {
        if (sum[i][a[x]] <= dd) cnt[i][sum[i][a[x]]]--;
        sum[i][a[x]]++;
        if (sum[i][a[x]] <= dd) cnt[i][sum[i][a[x]]]++;
      }
      if (sum[L][a[x]] == dd + 1) Q.insert(a[x]);
    }
  }
  return 0;
}
