#include
using namespace std;
struct node{
int data;
struct node* lc;
struct node* rc;
};
class BST{
struct node *root=NULL;
struct node* Inserting(struct node* Node,int a,long int p){
if(Node==NULL){
struct node* newnode=new node;
newnode->data=a;
newnode->lc=NULL;
newnode->rc=NULL;
Node=newnode;
cout<<p<<"\n";
}
else if (a<Node->data){
Node->lc=Inserting(Node->lc,a,2*p);
}
else if(a>Node->data){
Node->rc=Inserting(Node->rc,a,(2*p)+1);
}
return Node;
}
struct node* min(struct node* Node){
if(Node->lc==NULL)
return(Node);
else{
return min(Node->lc);
}
}
struct node* Deleting(struct node* Node,int a,long int p){
if(a<Node->data){
Node->lc=Deleting(Node->lc,a,2*p);
}
else if(a>Node->data){
Node->rc=Deleting(Node->rc,a,(2*p)+1);
}
else {
if(Node->lc==NULL && Node->rc==NULL){
delete Node;
cout<<p<<"\n";
Node=NULL;
}
else if(Node->lc==NULL ){
struct node* temp=Node->rc;
Node->data=temp->data;
cout<<p<<"\n";
delete temp;
temp=NULL;
}
else if(Node->rc==NULL){
struct node* temp=Node->lc;
Node->data=temp->data;
cout<<p<<"\n";
delete temp;
temp=NULL;
}
else {
struct node* temp=min(Node->rc);
Node->data=temp->data;
Deleting(Node->rc,temp->data,(2*p)+1);
}
}
return Node;
}
int checking(struct node* Node,int a){
if(a==Node->data){
return 1;
}
else if(a<Node->data){
return (checking(Node->lc,a));
}
else if(a>Node->data) {
return (checking(Node->rc,a));
}
else{
return 0;
}
}
public:
void Insert(int a){
root=Inserting(root,a,1);
}
int check(int a){
int present;
present=checking(root,a);
return present;
}
void Delete(int a){
Deleting(root,a,1);
}
};
int main() {
// your code goes here
int t;
BST tree;
cin>>t;
while(t){
char ch;
long long int x;
int i;
//for(i=0;i<2;i++)
// cin>>a[i];
cin>>ch;
cin>>x;
if(ch=='i'){
tree.Insert(x);
}
else if (ch=='d'){
int present=tree.check(x);
if(present==1){
tree.Delete(x);
}
}
t--;
}
return 0;
}