#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, SQ = 500;
int a[N], t[N], x[N], p[N], Cnt[2 * N][N / SQ + 5], T[N][N / SQ + 5], n;
vector<int> num;
void Build() {
  for (int i = 0; i < n; i++) {
    a[i] = lower_bound(num.begin(), num.end(), a[i]) - num.begin();
    Cnt[a[i]][i / SQ + 1]++;
  }
  for (int i = 0; i < 2 * N; i++)
    for (int b = 1; b * SQ < n + SQ; b++) Cnt[i][b] += Cnt[i][b - 1];
  int b = 1;
  while (b * SQ < n + SQ) {
    for (int i = 0; i < 2 * N; i++) T[Cnt[i][b]][b]++;
    for (int i = N - 2; i >= 0; i--) T[i][b] += T[i + 1][b];
    b++;
  }
}
void Change(int x, int y, int B) {
  T[Cnt[x][B]][B]--, Cnt[x][B]--, Cnt[y][B]++, T[Cnt[y][B]][B]++;
  return;
}
int Count(int idx) {
  int x = a[idx - 1];
  int res = Cnt[x][idx / SQ];
  while (idx % SQ != 0) res += (a[--idx] == x);
  return res;
}
int Get(int idx, int c) {
  int _idx = idx;
  int res = T[c][idx / SQ];
  while (idx % SQ != 0) {
    idx--;
    Cnt[a[idx]][idx / SQ]++;
    if (Cnt[a[idx]][idx / SQ] == c) res++;
  }
  idx = _idx;
  while (idx % SQ != 0) {
    idx--;
    Cnt[a[idx]][idx / SQ]--;
  }
  return res;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i], num.push_back(a[i]);
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> t[i] >> x[i] >> p[i], p[i]--;
    if (t[i] == 1) num.push_back(x[i]);
  }
  sort(num.begin(), num.end()),
      num.resize(unique(num.begin(), num.end()) - num.begin());
  Build();
  for (int i = 0; i < m; i++) {
    if (t[i] == 1) {
      int pos = p[i];
      x[i] = lower_bound(num.begin(), num.end(), x[i]) - num.begin();
      while (pos < n) Change(a[p[i]], x[i], pos / SQ + 1), pos += SQ;
      a[p[i]] = x[i];
      continue;
    }
    if (x[i] == 1) {
      cout << num[a[p[i]]] << "\n";
      continue;
    }
    int C = Count(p[i] + 1);
    if (x[i] % 2 == 0) {
      cout << C << "\n";
      continue;
    }
    cout << Get(p[i] + 1, C) << "\n";
  }
  return 0;
}
