1Da 2y。
不难发现发现 \(a_2=a_4=a_6=\cdots\)，\(a_3=a_5=a_7=\cdots\)，于是只需要维护前 \(3\) 行的值即可。
不难发现 \(a_{2,x}\) 为 \(a_{1,x}\) 在前缀中出现的次数，\(a_{3,x}\) 为 \(a_{1,x}\) 前缀中至少出现了 \(x\) 次的数的个数。
不难发现分块即可。
不难发现分块只需要维护 \(O(\sqrt n)\) 个块内 \(O(n)\) 个值，分别表示对于每种权值，在块的前缀中的出现次数。查询时继承 \(y\) 所在的块的前一个块的答案，然后剩下的一段后缀暴力跑即可。
// Problem: Tricky Password
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF418E
// Memory Limit: 500 MB
// Time Limit: 3500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define ins insert
#define era erase
typedef tuple<int, int, int> tu3;
typedef pair<int, int> pi;
inline int rd() {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void wr(int x) {
if (x < 0) x = ~(x - 1), putchar('-');
if (x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
}
using namespace vbzIO;
const int N = 1e5 + 100;
const int B = 350;
int n, m, b, len, a[N], t[N << 1];
int lp[B], rp[B], pos[N], c[B][N << 1], s[B][N];
struct qr {
int op, x, y;
qr () { }
qr (int _op, int _x, int _y) : op(_op), x(_x), y(_y) { }
} q[N];
void add(int x, int y) { c[x][y]++, s[x][c[x][y]]++; }
void del(int x, int y) { s[x][c[x][y]]--, c[x][y]--; }
vector<int> qry(int x) {
vector<int> res(2);
for (int i = lp[pos[x]]; i <= x; i++) add(pos[x] - 1, a[i]);
res[0] = c[pos[x] - 1][a[x]], res[1] = s[pos[x] - 1][res[0]];
for (int i = lp[pos[x]]; i <= x; i++) del(pos[x] - 1, a[i]);
return res;
}
int main() {
n = rd();
for (int i = 1; i <= n; i++)
a[i] = rd(), t[++len] = a[i];
m = rd();
for (int i = 1, op, x, y; i <= m; i++) {
op = rd(), x = rd(), y = rd(), q[i] = qr(op, x, y);
if (op == 1) t[++len] = x;
}
sort(t + 1, t + len + 1), len = unique(t + 1, t + len + 1) - t - 1;
for (int i = 1; i <= n; i++) a[i] = lower_bound(t + 1, t + len + 1, a[i]) - t;
for (int i = 1; i <= m; i++)
if (q[i].op == 1) q[i].x = lower_bound(t + 1, t + len + 1, q[i].x) - t;
b = sqrt(n);
for (int i = 1; i <= b; i++)
lp[i] = (i - 1) * b + 1, rp[i] = i * b;
if (rp[b] < n) b++, lp[b] = rp[b - 1] + 1, rp[b] = n;
for (int i = 1; i <= b; i++)
for (int j = lp[i]; j <= rp[i]; j++) pos[j] = i;
for (int i = 1; i <= b; i++) {
memcpy(c[i], c[i - 1], sizeof(int) * (len + 5));
memcpy(s[i], s[i - 1], sizeof(int) * (n + 5));
for (int j = lp[i]; j <= rp[i]; j++) add(i, a[j]);
}
for (int i = 1; i <= m; i++) {
int op = q[i].op, x = q[i].x, y = q[i].y;
if (op == 1) {
for (int j = pos[y]; j <= b; j++) del(j, a[y]); a[y] = x;
for (int j = pos[y]; j <= b; j++) add(j, a[y]);
} else {
if (x == 1) wr(t[a[y]]), pc('\n');
else wr(qry(y)[x & 1]), pc('\n');
}
}
return 0;
}