#include <bits/stdc++.h>
using namespace std;
int n, m, id, TBL;
int arr[100005], buf[100005], Rev[100005 + 100005];
int BIT[145][100005], tot[145];
int Freq[145][100005 + 100005], Fr[100005 + 100005];
map<int, int> Dis;
void BITupdate(int d, int x, int v) {
  if (x) {
    for (int i = x; i <= n; i += i & -i) BIT[d][i] += v;
    tot[d] += v;
  }
}
void update(int p, int v, int d) {
  int p1 = p / 700, t;
  for (int i = (p1); i < (TBL); i++) {
    int t = Freq[i][v];
    BITupdate(i, t, -1);
    Freq[i][v] += d;
    BITupdate(i, t + d, 1);
  }
}
int solve1(int p, int v) {
  int p1 = p / 700, p2 = p % 700, ret = 0;
  if (p1) ret += Freq[p1 - 1][v];
  for (int i = (0); i <= (p2); i++) ret += (arr[p - i] == v);
  return ret;
}
int BITcount(int d, int x) {
  int ret = tot[d];
  for (int i = x - 1; i; i -= i & -i) ret -= BIT[d][i];
  return ret;
}
int solve2(int p, int v) {
  int p1 = p / 700, p2 = p % 700, ret = 0;
  int fr = solve1(p, v);
  if (p1) ret = BITcount(p1 - 1, fr);
  for (int i = (1); i <= (p2); i++) {
    int t = arr[p - i];
    ++Fr[t];
    if (Fr[t] + (p1 ? Freq[p1 - 1][t] : 0) == fr) ++ret;
  }
  for (int i = (1); i <= (p2); i++) --Fr[arr[p - i]];
  return ret + 1;
}
int Mapto(int x) {
  if (Dis[x] == 0) {
    Dis[x] = ++id;
    Rev[id] = x;
  }
  return Dis[x];
}
int main() {
  scanf("%d", &n);
  for (int i = (0); i < (n); i++) scanf("%d", &arr[i]), arr[i] = Mapto(arr[i]);
  scanf("%d", &m);
  TBL = (n + 700 - 1) / 700;
  for (int i = (0); i < (n); i++) update(i, arr[i], 1);
  while (m--) {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y), --y;
    if (op == 1) {
      x = Mapto(x);
      update(y, arr[y], -1);
      update(y, x, 1);
      arr[y] = x;
    } else {
      if (x == 1)
        printf("%d\n", Rev[arr[y]]);
      else if ((x & 1) == 0)
        printf("%d\n", solve1(y, arr[y]));
      else
        printf("%d\n", solve2(y, arr[y]));
    }
  }
  return 0;
}
