#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int M = 105;
struct Query {
  int k, x, y;
  inline void input() {
    scanf("%d %d %d", &k, &x, &y);
    y--;
  }
} query[N];
int n, q, value[N], a[N], m = 0;
int cnt[M][N];
int prefix[M][N];
int sum[M][N];
int temp[N];
inline int lowbit(int x) { return x & (-x); }
inline void add(int *s, int pos, int val) {
  if (pos == 0) return;
  for (int i = pos; i <= n; i += lowbit(i)) {
    s[i] += val;
  }
}
inline int ask(int *s, int pos) {
  int ret = 0;
  for (int i = pos; i > 0; i -= lowbit(i)) {
    ret += s[i];
  }
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    value[m++] = a[i];
  }
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    query[i].input();
    if (query[i].k == 1) value[m++] = query[i].x;
  }
  sort(value, value + m);
  m = unique(value, value + m) - value;
  for (int i = 0; i < n; i++) {
    a[i] = lower_bound(value, value + m, a[i]) - value + 1;
  }
  for (int i = 0; i < q; i++) {
    if (query[i].k == 1)
      query[i].x = lower_bound(value, value + m, query[i].x) - value + 1;
  }
  int BLOCK = min((int)sqrt(n * 1.0 + 1e-8), 100),
      LEN = (n + BLOCK - 1) / BLOCK;
  for (int i = 0; i < n; i++) {
    int ID = i / LEN;
    prefix[ID][a[i]]++;
  }
  for (int j = 1; j <= m; j++) {
    for (int i = 1; i < BLOCK; i++) {
      prefix[i][j] += prefix[i - 1][j];
    }
  }
  for (int i = 0; i < BLOCK; i++) {
    for (int j = 1; j <= m; j++) {
      add(sum[i], prefix[i][j], 1);
    }
  }
  for (int i = 0; i < q; i++) {
    if (query[i].k == 1) {
      int ID = query[i].y / LEN;
      for (int j = ID; j < BLOCK; j++) {
        add(sum[j], prefix[j][a[query[i].y]], -1);
        prefix[j][a[query[i].y]]--;
        add(sum[j], prefix[j][a[query[i].y]], 1);
      }
      a[query[i].y] = query[i].x;
      for (int j = ID; j < BLOCK; j++) {
        add(sum[j], prefix[j][a[query[i].y]], -1);
        prefix[j][a[query[i].y]]++;
        add(sum[j], prefix[j][a[query[i].y]], 1);
      }
    } else {
      int ID = query[i].y / LEN,
          firstanswer = ID == 0 ? 0 : prefix[ID - 1][a[query[i].y]];
      for (int j = ID * LEN; j <= query[i].y; j++) {
        firstanswer += (a[query[i].y] == a[j]);
      }
      int secondanswer = 0;
      for (int j = ID * LEN; j <= query[i].y; j++) {
        temp[a[j]] = (ID == 0 ? 0 : prefix[ID - 1][a[j]]);
      }
      for (int j = ID * LEN; j <= query[i].y; j++) {
        temp[a[j]]++;
        if (temp[a[j]] == firstanswer) secondanswer++;
      }
      if (ID)
        secondanswer += ask(sum[ID - 1], n) - ask(sum[ID - 1], firstanswer - 1);
      if (query[i].x == 1) {
        printf("%d\n", value[a[query[i].y] - 1]);
      } else {
        if (query[i].x & 1) {
          printf("%d\n", secondanswer);
        } else
          printf("%d\n", firstanswer);
      }
    }
  }
  return 0;
}
