#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;
const int N = 2e5 + 100, sq = 2002, nsq = 100;
int cnt[nsq][N], b[nsq][N / 2];
int a[N];
map<int, int> mp, nmp;
vector<pair<int, pair<int, int> > > q;
void add(int id, int val) {
  while (id < nsq) {
    cnt[id][val]++;
    b[id][cnt[id][val]]++;
    id++;
  }
}
void rem(int id, int val) {
  while (id < nsq) {
    b[id][cnt[id][val]]--;
    cnt[id][val]--;
    id++;
  }
}
int get1(int id) {
  int val = a[id];
  int pid = id / sq;
  int ans = cnt[pid][val];
  int x = pid * sq;
  for (int i = x; i <= id; i++) {
    if (a[i] == val) ans++;
  }
  return ans;
}
int get2(int id) {
  int val = a[id];
  int pid = id / sq;
  int w = cnt[pid][val];
  int x = pid * sq;
  for (int i = x; i <= id; i++) {
    if (a[i] == val) w++;
  }
  int ans = b[pid][w];
  for (int i = x; i <= id; i++) {
    cnt[pid][a[i]]++;
    if (cnt[pid][a[i]] == w) ans++;
  }
  for (int i = x; i <= id; i++) {
    cnt[pid][a[i]]--;
  }
  return ans;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  vector<int> mol;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    mol.push_back(a[i]);
  }
  int q1;
  cin >> q1;
  for (int i = 0; i < q1; i++) {
    int t, u, v;
    cin >> t >> u >> v;
    if (t == 1) mol.push_back(u);
    q.push_back({t, {u, v - 1}});
  }
  sort(mol.begin(), mol.end());
  mol.resize(unique(mol.begin(), mol.end()) - mol.begin());
  for (int i = 0; i < mol.size(); i++) {
    mp[mol[i]] = i + 1;
    nmp[i + 1] = mol[i];
  }
  for (int i = 0; i < n; i++) a[i] = mp[a[i]];
  for (int i = 0; i < q1; i++)
    if (q[i].first == 1) q[i].second.first = mp[q[i].second.first];
  int id = 0;
  while (id < n) {
    for (int i = 0; i < id; i++) {
      cnt[id / sq][a[i]]++;
    }
    for (int i = 0; i < N; i++) {
      b[id / sq][cnt[id / sq][i]]++;
    }
    for (int i = N - 1; i; i--) {
      b[id / sq][i] += b[id / sq][i + 1];
    }
    id += sq;
  }
  for (int i = 0; i < q1; i++) {
    if (q[i].first == 1) {
      int v = q[i].second.first, p = q[i].second.second;
      int z = a[p];
      add(p / sq + 1, v);
      rem(p / sq + 1, a[p]);
      a[p] = v;
    } else {
      int x = q[i].second.first, y = q[i].second.second;
      if (x == 1)
        cout << nmp[a[y]] << '\n';
      else if (x % 2 == 0) {
        int ans = get1(y);
        cout << ans << '\n';
      } else {
        int ans = get2(y);
        cout << ans << '\n';
      }
    }
  }
}
