#include <bits/stdc++.h>
using namespace std;
const int mn = 101000, mm = 60;
int F[mm][mn * 2], G[mm][mn], A[mn], V[mn * 2];
int n, m, len, N, tt;
map<int, int> Q;
int get(int v) {
  if (!Q.count(v)) Q[v] = ++tt, V[tt] = v;
  return Q[v];
}
int main() {
  scanf("%d", &n);
  len = min((int)(6 * sqrt(n)), n), N = (n - 1) / len + 1;
  for (int i = 0; i <= n - 1; ++i) scanf("%d", A + i), A[i] = get(A[i]);
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= tt; ++j) F[i][j] = F[i - 1][j];
    for (int j = 1; j <= n; ++j) G[i][j] = G[i - 1][j];
    for (int j = (i - 1) * len; j <= min(i * len - 1, n - 1); ++j)
      ++G[i][++F[i][A[j]]];
  }
  scanf("%d", &m);
  for (; m--;) {
    int r, x, y, b;
    scanf("%d%d%d", &r, &x, &y);
    if (r == 1) {
      --y, b = y / len;
      for (int i = b + 1; i <= N; ++i) --G[i][F[i][A[y]]--];
      A[y] = get(x);
      for (int i = b + 1; i <= N; ++i) ++G[i][++F[i][A[y]]];
      continue;
    }
    --y, b = y / len;
    if (x == 1) {
      printf("%d\n", V[A[y]]);
      continue;
    }
    x = (x - 2) % 2 + 2;
    int v0 = F[b][A[y]];
    for (int i = b * len; i <= y; ++i)
      if (A[i] == A[y]) ++v0;
    if (x == 2) {
      printf("%d\n", v0);
      continue;
    }
    int v1 = G[b][v0];
    for (int i = b * len; i <= y; ++i)
      if (++F[b][A[i]] == v0) ++v1;
    printf("%d\n", v1);
    for (int i = b * len; i <= y; ++i) --F[b][A[i]];
  }
  return 0;
}
