#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
const int N = 1e5 + 100, block = 550;
int n, m, k, a[N], b[N * 2], w, t[N * 2];
int cnt[210][N * 2], f[210][N], l;
struct node {
  int op, x, y;
} q[N];
inline int lowbit(int x) { return x & (-x); }
inline void change(int id, int x, int v) {
  while (x > 0) {
    f[id][x] += v;
    x -= lowbit(x);
  }
}
inline int query(int id, int x) {
  int ans = 0;
  while (x <= m) {
    ans += f[id][x];
    x += lowbit(x);
  }
  return ans;
}
inline int read() {
  int f = 1, x = 0;
  char s = getchar();
  while (s < '0' || s > '9') {
    if (s == '-') f = -1;
    s = getchar();
  }
  while (s >= '0' && s <= '9') {
    x = x * 10 + s - '0';
    s = getchar();
  }
  return x * f;
}
int main() {
  m = read();
  for (int i = 1; i <= m; i++) a[i] = b[++w] = read();
  k = read();
  for (int i = 1; i <= k; i++) {
    q[i].op = 2 - read(), q[i].x = read(), q[i].y = read();
    if (q[i].op == 1) swap(q[i].x, q[i].y);
    if (q[i].op == 1) b[++w] = q[i].y;
  }
  sort(b + 1, b + 1 + w);
  w = unique(b + 1, b + 1 + w) - b - 1;
  for (int i = 1; i <= m; i++) a[i] = lower_bound(b + 1, b + w + 1, a[i]) - b;
  for (int i = 1; i <= k; i++)
    if (q[i].op == 1) q[i].y = lower_bound(b + 1, b + w + 1, q[i].y) - b;
  w = (m - 1) / block + 1;
  for (int i = 1; i <= w; i++) {
    memcpy(f[i], f[i - 1], sizeof(f[i]));
    memcpy(cnt[i], cnt[i - 1], sizeof(cnt[i]));
    for (int j = (i - 1) * block + 1; j <= min(m, i * block); j++) {
      change(i, cnt[i][a[j]], -1);
      cnt[i][a[j]]++;
      change(i, cnt[i][a[j]], 1);
    }
  }
  for (int i = 1; i <= k; i++) {
    if (q[i].op == 0) {
      if (q[i].x == 1) {
        printf("%d\n", b[a[q[i].y]]);
        continue;
      }
      int id = (q[i].y - 1) / block;
      for (int j = id * block + 1; j <= q[i].y; j++) {
        change(id, cnt[id][a[j]], -1);
        cnt[id][a[j]]++;
        change(id, cnt[id][a[j]], 1);
      }
      if (q[i].x & 1)
        printf("%d\n", query(id, cnt[id][a[q[i].y]]));
      else
        printf("%d\n", cnt[id][a[q[i].y]]);
      for (int j = q[i].y; j >= id * block + 1; j--) {
        change(id, cnt[id][a[j]], -1);
        cnt[id][a[j]]--;
        change(id, cnt[id][a[j]], 1);
      }
    } else {
      int id = (q[i].x - 1) / block + 1;
      for (int j = id; j <= w; j++) {
        change(j, cnt[j][a[q[i].x]], -1);
        cnt[j][a[q[i].x]]--;
        change(j, cnt[j][a[q[i].x]], 1);
        change(j, cnt[j][q[i].y], -1);
        cnt[j][q[i].y]++;
        change(j, cnt[j][q[i].y], 1);
      }
      a[q[i].x] = q[i].y;
    }
  }
}
