#include using namespace std; #define Loop(x,l,r) for (ll x = ll(l); x < ll(r); ++x) #define LoopR(x,l,r) for (ll x = ll(r)-1; x >= ll(l); --x) #define Looc(x,l,r) for (ll x = ll(l); x <= ll(r); ++x) #define LoocR(x,l,r) for (ll x = ll(r); x >= ll(l); --x) #define int ll typedef long long ll; typedef pair pii; typedef pair pll; #ifndef DB #define DB 0 #define endl '\n' #endif #define debugl(l) if constexpr ((l) < DB) #define debug debugl(0) const int N = 300'010*2; struct Fen { vector a; int n; void init(int sz) { n = sz; a.assign(n+1, {}); } void add(int i) { i++; while (i <= n) { a[i]++; i += i&-i; } } int index(int x) { int p = 1<<__lg(n); int i = 0; while (p) { if (i + p <= n && x >= a[i + p]) { x -= a[i + p]; i += p; } p /= 2; } return i; } }; void solve() { int n; cin >> n; vector a(n); for (auto &x : a) { cin >> x; x--; } int q; cin >> q; vector qu(q); for (auto &[x, y] : qu) { cin >> x; if (x != 2) { cin >> y; y--; } } list ls; vector::iterator> its(n); for (int x : a) its[x] = ls.insert(ls.end(), x); for (auto [t, p] : qu) { if (t != 1) continue; auto it = p == -1? ls.end(): its[p]; its.push_back(ls.insert(it, its.size())); } vector b(ls.begin(), ls.end()); n = b.size(); vector bp(n); Loop (i,0,n) bp[b[i]] = i; debug { for (int x : b) cerr << x << ' '; cerr << "???\n"; } Fen fen; fen.init(n); for (int x : a) fen.add(bp[x]); int base = 0; int cnt = a.size(); for (auto [t, p] : qu) { if (t == 1) fen.add(bp[cnt++]); if (t == 2) base++; if (t == 3) { int i = fen.index(base + p); debug cerr << i << "!\n"; cout << b[i] + 1 << '\n'; } } } signed main() { cin.tie(0) -> sync_with_stdio(false); int t = 1; //cin >> t; while (t--) solve(); }