#include using namespace std; #include #include using namespace __gnu_pbds; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; #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) 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"; } ordered_set s; for (int x : a) s.insert({bp[x], x}); int base = 0; int cnt = a.size(); for (auto [t, p] : qu) { if (t == 1) { s.insert({bp[cnt], cnt}); cnt++; } if (t == 2) base++; if (t == 3) { auto [i, x] = *s.find_by_order(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(); }