#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int S = 1000;
inline int IN() {
  char ch;
  (ch = getchar());
  int f = 0, x = 0;
  for (; ((ch) == '\n' || (ch) == '\r' || (ch) == '\t' || (ch) == ' ');
       (ch = getchar()))
    ;
  if (ch == '-') f = 1, (ch = getchar());
  for (; !((ch) == '\n' || (ch) == '\r' || (ch) == '\t' || (ch) == ' ');
       (ch = getchar()))
    x = x * 10 + ch - '0';
  return (f) ? (-x) : (x);
}
int n, val[N], a[N], F[105][N], G[105][N], tot, D;
map<int, int> mps;
int uni(int t) {
  if (!mps.count(t)) val[D] = t, mps[t] = D++;
  return mps[t];
}
int main() {
  n = IN();
  for (int i = (int)0; i < (int)n; i++) a[i] = uni(IN());
  for (int i = 0; i < n; i += S) {
    int r = min(n, i + S);
    int t = ++tot;
    for (int j = (int)0; j < (int)D; j++) F[t][j] = F[t - 1][j];
    for (int j = (int)0; j < (int)i + 1; j++) G[t][j] = G[t - 1][j];
    for (int j = (int)i; j < (int)r; j++) G[t][++F[t][a[j]]]++;
  }
  ++tot;
  int m = IN();
  while (m--) {
    int k = IN(), x = IN(), y = IN();
    if (k == 1) {
      int id = (--y) / S + 1;
      for (int i = (int)id; i < (int)tot; i++) G[i][F[i][a[y]]--]--;
      a[y] = uni(x);
      for (int i = (int)id; i < (int)tot; i++) G[i][++F[i][a[y]]]++;
    } else {
      int id = (--y) / S, fir = id * S;
      if (x == 1) {
        printf("%d\n", val[a[y]]);
        continue;
      }
      for (int i = (int)fir; i < (int)y + 1; i++) G[id][++F[id][a[i]]]++;
      printf("%d\n", (x % 2 == 0) ? (F[id][a[y]]) : (G[id][F[id][a[y]]]));
      for (int i = (int)fir; i < (int)y + 1; i++) G[id][F[id][a[i]]--]--;
    }
  }
  return 0;
}
