#include "bits/stdc++.h" using namespace std; using ll=long long; using dd=double; using vll=vector< ll>; using vdd=vector< dd>; using vvll=vector< vll>; using vvdd=vector; using vvvll=vector< vvll>; using vvvdd=vector; using vvvvll=vector; using pll=pair; using tll=tuple; using qll=tuple; using vpll=vector< pll>; using vtll=vector< tll>; using vqll=vector< qll>; using vvpll=vector; using vvtll=vector; using vvqll=vector; constexpr ll INF = 1LL << 60; struct Fast{ Fast(){ cin.tie(0); ios::sync_with_stdio(false); cout<::max_digits10); } } fast; #define REPS(i, S, E) for (ll i = (S); i <= (E); i++) #define REP(i, N) REPS(i, 0, (N)-1) #define DEPS(i, S, E) for (ll i = (E); i >= (S); i--) #define DEP(i, N) DEPS(i, 0, (N)-1) #define rep(i, S, E) for (ll i = (S); i <= (E); i++) #define dep(i, E, S) for (ll i = (E); i >= (S); i--) #define each(e, v) for (auto&& e : v) #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() template inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; }return false; } template inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; }return false; } template inline T MaxE(vector&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmax(m,v[i]); return m; } template inline T MinE(vector&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmin(m,v[i]); return m; } template inline T MaxE(vector &v) { return MaxE(v,0,(ll)v.size()-1); } template inline T MinE(vector &v) { return MinE(v,0,(ll)v.size()-1); } template inline T Sum(vector &v,ll S,ll E){ T s=T(); rep(i,S,E)s+=v[i]; return s; } template inline T Sum(vector &v) { return Sum(v,0,v.size()-1); } template inline ll sz(T &v){ return (ll)v.size(); } inline ll CEIL(ll a,ll b){ return (a<0) ? -(-a/b) : (a+b-1)/b; } inline ll FLOOR(ll a,ll b){ return -CEIL(-a,b); } //pair用テンプレート using vpll=vector< pll>; using vvpll=vector; template inline pair& operator+=(pair &a,const pair &b){ a.first+=b.first; a.second+=b.second; return a; } template inline pair& operator-=(pair &a,const pair &b){ a.first-=b.first; a.second-=b.second; return a; } template inline pair& operator*=(pair &a,const pair &b){ a.first*=b.first; a.second*=b.second; return a; } template inline pair& operator/=(pair &a,const pair &b){ a.first/=b.first; a.second/=b.second; return a; } template inline pair& operator%=(pair &a,const pair &b){ a.first%=b.first; a.second%=b.second; return a; } template inline pair& operator+=(pair &a,R b){ a.first+=b; a.second+=b; return a; } template inline pair& operator-=(pair &a,R b){ a.first-=b; a.second-=b; return a; } template inline pair& operator*=(pair &a,R b){ a.first*=b; a.second*=b; return a; } template inline pair& operator/=(pair &a,R b){ a.first/=b; a.second/=b; return a; } template inline pair& operator%=(pair &a,R b){ a.first%=b; a.second%=b; return a; } template inline pair operator+(const pair &a,R b){ pair c=a; return c+=b; } template inline pair operator-(const pair &a,R b){ pair c=a; return c-=b; } template inline pair operator*(const pair &a,R b){ pair c=a; return c*=b; } template inline pair operator/(const pair &a,R b){ pair c=a; return c/=b; } template inline pair operator%(const pair &a,R b){ pair c=a; return c%=b; } template inline pair operator-(R b,const pair &a){ pair c=-a; return c+=b; } template inline pair operator-(const pair &a){ pair c=a; return c*=(-1); } template inline ostream &operator<<(ostream &os,const pair &a){ return os << a.first << ' ' << a.second; } //vector用テンプレート template inline vector& operator+=(vector &a,const vector &b){ for (ll i=0; i<(ll)a.size(); i++) a[i]+=b[i]; return a; } template inline vector& operator-=(vector &a,const vector &b){ for (ll i=0; i<(ll)a.size(); i++) a[i]-=b[i]; return a; } template inline vector& operator*=(vector &a,const vector &b){ for (ll i=0; i<(ll)a.size(); i++) a[i]*=b[i]; return a; } template inline vector& operator/=(vector &a,const vector &b){ for (ll i=0; i<(ll)a.size(); i++) a[i]/=b[i]; return a; } template inline vector& operator%=(vector &a,const vector &b){ for (ll i=0; i<(ll)a.size(); i++) a[i]%=b[i]; return a; } template inline vector& operator+=(vector &a,S b){ for (T &e: a) e+=b; return a; } template inline vector& operator-=(vector &a,S b){ for (T &e: a) e-=b; return a; } template inline vector& operator*=(vector &a,S b){ for (T &e: a) e*=b; return a; } template inline vector& operator/=(vector &a,S b){ for (T &e: a) e/=b; return a; } template inline vector& operator%=(vector &a,S b){ for (T &e: a) e%=b; return a; } template inline vector operator+(const vector &a,S b){ vector c=a; return c+=b; } template inline vector operator-(const vector &a,S b){ vector c=a; return c-=b; } template inline vector operator*(const vector &a,S b){ vector c=a; return c*=b; } template inline vector operator/(const vector &a,S b){ vector c=a; return c/=b; } template inline vector operator%(const vector &a,S b){ vector c=a; return c%=b; } template inline vector operator-(S b,const vector &a){ vector c=-a; return c+=b; } template inline vector operator-(const vector &a){ vector c=a; return c*=(-1); } template inline ostream &operator<<(ostream &os,const vector &a){ for (ll i=0; i<(ll)a.size(); i++) os<<(i>0?" ":"")< struct mll_{ ll val; mll_(ll v = 0): val(v % MOD){ if (val < 0) val += MOD; } mll_ operator - () const { return -val; } mll_ operator + (const mll_ &b) const { return val + b.val; } mll_ operator - (const mll_ &b) const { return val - b.val; } mll_ operator * (const mll_ &b) const { return val * b.val; } mll_ operator / (const mll_ &b) const { return mll_(*this) /= b; } mll_ operator + (ll b) const { return *this + mll_(b); } mll_ operator - (ll b) const { return *this - mll_(b); } mll_ operator * (ll b) const { return *this * mll_(b); } friend mll_ operator + (ll a,const mll_ &b) { return b + a; } friend mll_ operator - (ll a,const mll_ &b) { return -b + a; } friend mll_ operator * (ll a,const mll_ &b) { return b * a; } friend mll_ operator / (ll a,const mll_ &b) { return mll_(a)/b; } mll_ &operator += (const mll_ &b) { val=(val+b.val)%MOD; return *this; } mll_ &operator -= (const mll_ &b) { val=(val+MOD-b.val)%MOD; return *this; } mll_ &operator *= (const mll_ &b) { val=(val*b.val)%MOD; return *this; } mll_ &operator /= (const mll_ &b) { ll c=b.val,d=MOD,u=1,v=0; while (d){ ll t = c / d; c -= t * d; swap(c,d); u -= t * v; swap(u,v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } mll_ &operator += (ll b) { return *this += mll_(b); } mll_ &operator -= (ll b) { return *this -= mll_(b); } mll_ &operator *= (ll b) { return *this *= mll_(b); } mll_ &operator /= (ll b) { return *this /= mll_(b); } bool operator == (const mll_ &b) const { return val == b.val; } bool operator != (const mll_ &b) const { return val != b.val; } bool operator == (ll b) const { return *this == mll_(b); } bool operator != (ll b) const { return *this != mll_(b); } friend bool operator == (ll a,const mll_ &b) { return mll_(a) == b.val; } friend bool operator != (ll a,const mll_ &b) { return mll_(a) != b.val; } friend ostream &operator << (ostream &os,const mll_ &a) { return os << a.val; } friend istream &operator >> (istream &is,mll_ &a) { return is >> a.val; } static mll_ Combination(ll a,ll b){ chmin(b,a-b); if (b<0) return mll_(0); mll_ c = 1; rep(i,0,b-1) c *= a-i; rep(i,0,b-1) c /= i+1; return c; } }; //using mll = mll_<1000000007LL>; using mll = mll_<998244353LL>; using vmll = std::vector; using vvmll = std::vector; using vvvmll = std::vector; using vvvvmll = std::vector; #if 0 #include using namespace atcoder; #endif struct coordinateCompression{ map val2idx; vll idx2val; coordinateCompression(){} void add(ll val){ val2idx[val]=0; } void add(vll v){ each(e, v) val2idx[e]=0; } void compress(){ ll cnt=0; each(e, val2idx){ idx2val.push_back(e.first); e.second=cnt++; } } ll size(){ return (ll)idx2val.size(); } ll v2i(ll v){ return val2idx[v]; } ll i2v(ll i){ return idx2val[i]; } bool contains(ll v){ return val2idx.count(v) == 1; } }; template struct BIT_{ vector v; ll N; BIT_(){} BIT_(ll N) { init(N); } void init(ll N) { v.resize(N+1); this->N = N; } void add(ll i, T x) { for (i++; i<=N; i+=i&(-i)) v[i]+=x; } T sum(ll i) { T s=0; for (i++; i>0; i-=i&(-i)) s+=v[i]; return s; } T sum(ll i, ll j) { return sum(j)-sum(i-1); } T sum() { return sum(N-1); } //総和 T operator[](ll i) { return sum(i,i); } ll lower_bound(T s){ ll i=0,l=1; while (l0; l>>=1) if(i+l<=N && v[i+l]= 1; } //x∈集合ならtrue ll rank(ll x) { return sum(x-1)+1; }//xが小さい方から何番目か 1-origin ll rrank(ll x) { return sum(x+1,N-1)+1; }//xが大きい方から何番目か 1-origin ll leftnumof(ll x) { return sum(x); }//x以下の個数 ll rightnumof(ll x) { return sum(x,N-1); }//x以上の個数 ll nthsmall(ll r) { return lower_bound(r); } //r番目に小さい要素 1-origin ll nthbig(ll r) { return (size(); //座圧版集合管理BIT struct BITCO{ BIT_ bit; coordinateCompression co; BITCO(){} BITCO(vll &v){ init(v); } void init(vll &v){ co.add(v); co.compress(); bit.init(co.size()); } ll size() { return bit.size(); } //要素数 void insert(ll x) { bit.insert(co.v2i(x)); }//集合にx追加 void erase(ll x) { bit.erase(co.v2i(x)); }//集合からx1つ削除 bool contains(ll x) { return co.contains(x) ? bit.contains(co.v2i(x)) : false; } ll operator[](ll x){ return co.contains(x) ? bit[co.v2i(x)] : 0; } //xの個数 ll rank(ll x) { return bit.rank(co.v2i(x)); }//xが小さい方から何番目か 1-origin ll rrank(ll x) { return bit.rrank(co.v2i(x)); }//xが大きい方から何番目か 1-origin ll leftnumof(ll x) { return bit.leftnumof(co.v2i(x)); }//x以下の個数 ll rightnumof(ll x) { return bit.rightnumof(co.v2i(x)); }//x以上の個数 ll nthsmall(ll r){ //r番目に小さい要素 1-origin ない時はINF ll i=bit.nthsmall(r); return (i==bit.N) ? INF : co.i2v(i); } ll nthbig(ll r){ //r番目に大きい要素 1-origin ない時は-INF ll i=bit.nthbig(r); return (i==-1) ? -INF : co.i2v(i); } void Dump() { rep(i,0,bit.N-1) cerr<> q >> k; vector> kv(q); vll buf; rep(i,0,q-1){ ll k; ll v=-1; cin>>k; if (k==1) cin >> v; kv[i]={k,v}; if (k==1)buf.push_back(v); } BITCO bit(buf); vll ans; rep(i,0,sz(kv)-1){ ll kind,v; tie(kind,v) = kv[i]; if (kind==1){ bit.insert(v); } else{//kind==2 ll x=bit.nthsmall(k); if (x==INF){ ans.push_back(-1); } else{ ans.push_back(x); bit.erase(x); } } } each(e,ans) cout << e << '\n'; return; } int main(){ #if 1 solve(); //cin2solve(); //generand(); #else ll t; cin >> t; rep(i, 0, t-1){ solve(); //cin2solve(); } #endif return 0; }