#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 5;
const int SQ = 2e3 + 5;
const int BN = maxN / SQ + 5;
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
int n;
int fen[BN][maxN], type[maxN];
int a[maxN], arumin[BN][maxN];
pair<int, int> Q[maxN];
vector<int> vec;
void put(int id, int p, int x) {
  for (p++; p < maxN; p += (p & -p)) fen[id][p] += x;
  return;
}
int fetch(int id, int p) {
  int tmp = 0;
  for (p++; p > 0; p -= (p & -p)) tmp += fen[id][p];
  return tmp;
}
void build(int id) {
  int L = id * SQ;
  int R = min(L + SQ, n);
  if (id)
    for (int i = 0; i < maxN; i++) arumin[id][i] = arumin[id - 1][i];
  for (int i = L; i < R; i++) arumin[id][a[i]]++;
  for (int i = 0; i < maxN; i++) put(id, arumin[id][i], +1);
  return;
}
int main() {
  time_t START = clock();
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
    vec.push_back(a[i]);
  }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d%d%d", type + i, &Q[i].first, &Q[i].second);
    Q[i].second--;
    if (type[i] == 1) vec.push_back(Q[i].first);
  }
  sort(vec.begin(), vec.end());
  vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
  for (int i = 0; i < n; i++)
    a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
  for (int i = 0; i < q; i++)
    if (type[i] == 1)
      Q[i].first =
          lower_bound(vec.begin(), vec.end(), Q[i].first) - vec.begin();
  for (int i = 0; i * SQ < n; i++) build(i);
  for (int i = 0; i < q; i++) {
    int id = Q[i].second / SQ;
    int &x = a[Q[i].second];
    if (type[i] == 1) {
      for (int i = id; i * SQ < n; i++) {
        put(i, arumin[i][x], -1);
        arumin[i][x]--;
        put(i, arumin[i][x], +1);
      }
      x = Q[i].first;
      for (int i = id; i * SQ < n; i++) {
        put(i, arumin[i][x], -1);
        arumin[i][x]++;
        put(i, arumin[i][x], +1);
      }
    } else {
      if (Q[i].first == 1) {
        printf("%d\n", vec[x]);
        continue;
      }
      Q[i].first &= 1;
      int res = (id ? arumin[id - 1][x] : 0);
      for (int j = id * SQ; j <= Q[i].second; j++) res += (a[j] == x);
      if (Q[i].first) {
        int tmp = (id ? fetch(id - 1, maxN - 1) - fetch(id - 1, res - 1) : 0);
        int pid = (BN + id - 1) % BN;
        for (int j = id * SQ; j <= Q[i].second; j++) {
          arumin[pid][a[j]]++;
          tmp += (arumin[pid][a[j]] == res);
        }
        swap(res, tmp);
        for (int j = id * SQ; j <= Q[i].second; j++) arumin[pid][a[j]]--;
      }
      printf("%d\n", res);
    }
  }
  time_t FINISH = clock();
  cerr << "Execution time: "
       << (long double)(FINISH - START) / CLOCKS_PER_SEC * 1000.0
       << " milliseconds.\n";
  return 0;
}
