#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bc back()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const ll inf=1e18+7;
const ll mod=998244353;
const ll N=130*2;;
const ld eps=1e-9;
struct node{
ll a,h,h2,hh;
node* l;
node* r;
};
node* newp(ll a){
node* b=new node();
b->a=a;
b->h=b->h2=0ll;
b->hh=1ll;
b->l=b->r=NULL;
return b;
}
node* next(node* v,ll a){
if(v==NULL) return v;
if(a>=v->a){
return next(v->r,a);
}else{
if(v->l==NULL) return v;
node* x=next(v->l,a);
if(x==NULL || x->a<=a) return v;
return x;
}
}
node* prev(node* v,ll a){
if(v==NULL) return NULL;
if(a>v->a){
if(v->r==NULL) return v;
node* x=prev(v->r,a);
if(x==NULL || x->a>=a) return v;
return x;
}else{
return prev(v->l,a);
}
}
bool check(node* v,ll a){
if(v==NULL) return false;
if(v->a==a) return true;
if(a>v->a) return check(v->r,a);
else return check(v->l,a);
}
node* bal(node* v){
if(abs(v->h-v->h2)<2)return v;
if(v->h2>v->h){
node* b=v->r;
if(b->h2>b->h){
v->r=b->l;
b->l=v;
if(v->l!=NULL)v->h=v->l->hh;
if(v->r!=NULL)v->h2=v->r->hh;
v->hh=max(v->h,v->h2)+1;
if(b->l!=NULL)b->h=b->l->hh;
if(b->r!=NULL)b->h2=b->r->hh;
b->hh=max(b->h,b->h2)+1;
return b;
}
else{
node* z=b->l;
v->r=z->l;
b->l=z->r;
z->l=v;
z->r=b;
if(z->l!=NULL)z->h=z->l->hh;
if(z->r!=NULL)z->h2=z->r->hh;
z->hh=max(z->h,z->h2)+1;
if(v->l!=NULL)v->h=v->l->hh;
if(v->r!=NULL)v->h2=v->r->hh;
v->hh=max(v->h,v->h2)+1;
if(b->l!=NULL)b->h=b->l->hh;
if(b->r!=NULL)b->h2=b->r->hh;
b->hh=max(b->h,b->h2)+1;
return z;
}
}else{
node* b=v->l;
if(b->h>b->h2){
v->l=b->r;
b->r=v;
if(v->l!=NULL)v->h=v->l->hh;
if(v->r!=NULL)v->h2=v->r->hh;
v->hh=max(v->h,v->h2)+1;
if(b->l!=NULL)b->h=b->l->hh;
if(b->r!=NULL)b->h2=b->r->hh;
b->hh=max(b->h,b->h2)+1;
return b;
}
else{
node* z=b->r;
v->l=z->r;
b->r=z->l;
z->r=v;
z->l=b;
if(z->l!=NULL)z->h=z->l->hh;
if(z->r!=NULL)z->h2=z->r->hh;
z->hh=max(z->h,z->h2)+1;
if(v->l!=NULL)v->h=v->l->hh;
if(v->r!=NULL)v->h2=v->r->hh;
v->hh=max(v->h,v->h2)+1;
if(b->l!=NULL)b->h=b->l->hh;
if(b->r!=NULL)b->h2=b->r->hh;
b->hh=max(b->h,b->h2)+1;
return z;
}
}
}
node* ins(node* v,ll a){
if(v==NULL){
return newp(a);
}
if(a==v->a) return v;
else if(a>v->a){
v->r=ins(v->r,a);
if(v->r!=NULL)v->h2=v->r->hh;
}else{
v->l=ins(v->l,a);
if(v->l!=NULL)v->h=v->l->hh;
}
v->hh=max(v->h,v->h2)+1ll;
v=bal(v);
return v;
}
node* mx(node* v){
if(v->r==NULL){
return v;
}else {
node* b=mx(v->r);
if(b==v->r) v->r=b->l;
if(v->r!=NULL) v->h2=v->r->hh;
v->hh=max(v->h,v->h2)+1ll;
v=bal(v);
return b;
}
}
node* del(node* v,ll a){
if(v==NULL){
return v;
}
if(a==v->a) {
if(v->l==NULL && v->r==NULL)return NULL;
if(v->l==NULL) return v->r;
if(v->r==NULL) return v->l;
node* b=mx(v->l);
if(v->l!=b && b!=NULL)b->l=v->l;
if(b!=NULL)b->r=v->r;
if(b!=NULL)b=bal(b);
return b;
}
else if(a>v->a){
v->r=del(v->r,a);
if(v->r!=NULL)v->h2=v->r->hh;
}else{
v->l=del(v->l,a);
if(v->l!=NULL)v->h=v->l->hh;
}
v->hh=max(v->h,v->h2)+1;
v=bal(v);
return v;
}
void solve(){
ll b;
node* r=NULL;
str s;
while(cin>>s){
cin>>b;
if(s=="insert"){
r=ins(r,b);
}else if(s=="delete"){
r=del(r,b);
}else if(s=="exists"){
if(check(r,b))cout<<"true"<<endl;
else cout<<"false"<<endl;
}else if(s=="next"){
if(next(r,b)==NULL)cout<<"none"<<endl;
else cout<<next(r,b)->a<<endl;
}else{
if(prev(r,b)==NULL)cout<<"none"<<endl;
else cout<<prev(r,b)->a<<endl;
}
}
}
signed main(){
start();
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ll t=1;
//cin>>t;
while(t--) solve();
}
/*
insert 1
insert 2
insert 3
insert 4
insert 5
insert 6
insert 7
insert 8
*/
