#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
using namespace std;
long long poww(long long a, long long b, long long md) {
  return (!b ? 1
             : (b & 1 ? a * poww(a * a % md, b / 2, md) % md
                      : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 2000 * 100 + 5;
const long long inf = 9223372036854775807;
const long long mod = 1e9 + 7;
const int lg = 20;
const int SQ = 6000;
const int sq = maxn / SQ + 2;
int cnt[sq][maxn], fen[sq][maxn], type[maxn], v[maxn], p[maxn], res, n, q,
    a[maxn], num[maxn], mark[maxn], ans2, ans3, ans, c[maxn];
vector<int> comp;
unordered_map<int, int> to;
void add(int pos, int i, int val) {
  for (i++; i < maxn; i += i & -i) fen[pos][i] += val;
}
int get(int pos, int i) {
  res = 0;
  for (i++; i > 0; i -= i & -i) res += fen[pos][i];
  return res;
}
void build() {
  for (int i = 1; i <= n; i++) {
    cnt[i / SQ][a[i]]++;
  }
  for (int i = 1; i <= n; i++) {
    if (mark[a[i]]) continue;
    mark[a[i]] = 1;
    for (int j = 1; j < sq; j++) {
      cnt[j][a[i]] += cnt[j - 1][a[i]];
    }
  }
  for (int i = 0; i < sq; i++) {
    for (int j = 1; j <= (long long)(comp).size(); j++) {
      add(i, cnt[i][j], 1);
    }
  }
}
void del(int x) {
  for (int i = x / SQ; i < sq; i++) {
    add(i, cnt[i][a[x]], -1);
    add(i, --cnt[i][a[x]], 1);
  }
}
void Add(int x) {
  for (int i = x / SQ; i < sq; i++) {
    add(i, cnt[i][a[x]], -1);
    add(i, ++cnt[i][a[x]], 1);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    comp.push_back(a[i]);
  }
  cin >> q;
  for (int i = 1; i <= q; i++) {
    cin >> type[i] >> v[i] >> p[i];
    if (type[i] == 1) comp.push_back(v[i]);
    if (type[i] == 2) {
      if (v[i] > 3) {
        if (v[i] & 1)
          v[i] = 3;
        else
          v[i] = 2;
      }
    }
  }
  sort((comp).begin(), (comp).end());
  comp.resize(unique((comp).begin(), (comp).end()) - comp.begin());
  for (int i = 0; i < (long long)(comp).size(); i++) {
    to[comp[i]] = i + 1;
    num[i + 1] = comp[i];
  }
  for (int i = 1; i <= n; i++) a[i] = to[a[i]];
  for (int i = 1; i <= q; i++) {
    if (type[i] == 1) v[i] = to[v[i]];
  }
  build();
  int x, y, t, ct = 0;
  for (int i = 1; i <= q; i++) {
    ct += (type[i] == 2);
    if (type[i] == 1) {
      del(p[i]);
      a[p[i]] = v[i];
      Add(p[i]);
      continue;
    }
    x = v[i], y = p[i];
    if (x == 1) {
      cout << num[a[y]] << "\n";
      continue;
    }
    ans = a[y];
    if (y / SQ > 0)
      ans2 = cnt[y / SQ - 1][ans];
    else
      ans2 = 0;
    for (int j = y - (y % SQ); j <= y; j++) {
      if (a[j] == a[y]) ans2++;
    }
    if (x == 2) {
      cout << ans2 << "\n";
      continue;
    }
    if (y / SQ > 0)
      ans3 = get(y / SQ - 1, maxn / 2) - get(y / SQ - 1, ans2 - 1);
    else {
      ans3 = 0;
      for (int j = 1; j <= y; j++) {
        c[a[j]]++;
        if (c[a[j]] == ans2) ans3++;
      }
      for (int j = 1; j <= y; j++) c[a[j]]--;
      cout << ans3 << "\n";
      continue;
    }
    t = y / SQ - 1;
    for (int j = y - (y % SQ); j <= y; j++) {
      cnt[t][a[j]]++;
      if (cnt[t][a[j]] == ans2) ans3++;
    }
    for (int j = y - (y % SQ); j <= y; j++) cnt[t][a[j]]--;
    cout << ans3 << "\n";
  }
}
