#include <bits/stdc++.h>
using namespace std;
const int S = 1000;
int a[100010], f[110][200010], g[110][200010], val[200010], M;
map<int, int> mp;
int num(int x) {
  if (mp.find(x) == mp.end()) {
    M++;
    mp[x] = M;
    val[M] = x;
  }
  return mp[x];
}
int n, m, i, j, x, y, z;
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &x);
    a[i] = num(x);
  }
  x = 0;
  for (i = 1; i <= n; i += S) {
    z = min(i + S - 1, n);
    memcpy(f[(i - 1) / S + 1], f[(i - 1) / S], sizeof(f[(i - 1) / S]));
    memcpy(g[(i - 1) / S + 1], g[(i - 1) / S], sizeof(f[(i - 1) / S]));
    for (j = i; j <= z; j++) {
      f[(i - 1) / S + 1][a[j]]++;
      g[(i - 1) / S + 1][f[(i - 1) / S + 1][a[j]]]++;
    }
  }
  scanf("%d", &m);
  while (m--) {
    scanf("%d%d%d", &i, &x, &y);
    if (i == 1) {
      for (i = (y - 1) / S + 1; (i - 1) * S + 1 <= n; i++) {
        g[i][f[i][a[y]]]--;
        f[i][a[y]]--;
      }
      a[y] = num(x);
      for (i = (y - 1) / S + 1; (i - 1) * S + 1 <= n; i++) {
        f[i][a[y]]++;
        g[i][f[i][a[y]]]++;
      }
    } else {
      if (x == 1) {
        printf("%d\n", val[a[y]]);
        continue;
      }
      for (i = (y - 1) / S * S + 1; i <= y; i++) {
        f[(y - 1) / S][a[i]]++;
        g[(y - 1) / S][f[(y - 1) / S][a[i]]]++;
      }
      printf("%d\n", (x & 1) ? g[(y - 1) / S][f[(y - 1) / S][a[y]]]
                             : f[(y - 1) / S][a[y]]);
      for (i = (y - 1) / S * S + 1; i <= y; i++) {
        g[(y - 1) / S][f[(y - 1) / S][a[i]]]--;
        f[(y - 1) / S][a[i]]--;
      }
    }
  }
  return 0;
}
