#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
typedef struct Avl{
  int value;
  int height;
  int nChild;
  struct Avl* left;
  struct Avl* right;
}Avl;
Avl* AvlNew(Avl* avl,int value);
Avl* AvlInsert(Avl* avl, int value);
Avl* AvlDelete(Avl* avl,int value);
void KLess(Avl* avl,int k);
void KIndex(Avl* avl,int k);

static void RecKIndex(Avl* avl,int k,int* s){
  if(avl->left == NULL && *s + 1 == k)
    printf("%d"   , avl->value);
  else{
    if(avl->left != NULL &&(avl->left->nChild + 2 + *s) == k)
      printf("%d  ", avl->value);
    if(avl->left != NULL && avl->left->nChild + 2 < k){
      *s = avl->left->nChild + 2;
      if(avl->right != NULL)
	RecKIndex(avl->right,k,s);
    }
    else
      if(avl->left != NULL)
	RecKIndex(avl->left,k,s);
  }
}
void KIndex(Avl* avl, int k){
  if(avl == NULL || avl->nChild < k - 1){
    printf("invalid \n");
  }
  int s = 0;
  RecKIndex(avl,k,&s);
}
static void RecKLess(Avl* avl, int k, int* sum){
  if(avl == NULL)
    return;
  if(k > avl->value){
    if(avl->left != NULL)
      *sum += avl->left->nChild + 1;
    (*sum)++;
    RecKLess(avl->right,k,sum);
  }
  if(k <= avl->value){
    RecKLess(avl->left,k,sum);
  }
}
void KLess(Avl* avl,int k){
  int sum = 0;
  RecKLess(avl,k,&sum);
  printf("%d \n",sum);
}
Avl* AvlNew(Avl* avl, int value){
  avl = (Avl*)malloc(sizeof(Avl));
  avl->value  = value ;
  avl->left   = NULL;
  avl->nChild = 0;
  avl->right  = NULL;
  avl->height = 1;
  return avl;
}
static int height(Avl* avl){
  return avl == NULL ? 0 : avl->height;
}
static int max(int avl1, int avl2){
  return avl1 > avl2 ? avl1 : avl2 ;
}
static int nChildCur(Avl* avl){
  int l = 0;
  int r = 0;
  if(avl ->left != NULL)
    l = avl->left->nChild + 1;
  if(avl -> right != NULL)
    r = avl->right ->nChild +1;
  return l+r;
}

static Avl* rightRotate(Avl* avl){
  Avl* left = avl->left;
  Avl* Lright = left->right;
  left->right = avl;
  avl->left = Lright;
  avl->height = max(height(avl->left),height(avl->right))+1;
  left->height = max(height(left->left),height(left->right))+1;
  avl->nChild = nChildCur(avl);
  left->nChild = nChildCur(left);
  avl = left;
  return avl;
}

static Avl* leftRotate(Avl* avl){
  Avl* right = avl->right;
  Avl* Rleft = right->left;
  right->left = avl;
  avl->right = Rleft;
  avl->height = max(height(avl->left),(height(avl->right)))+1;
  right->height = max(height(right->left),height(right->right))+1;
  avl->nChild = nChildCur(avl);
  right->nChild = nChildCur(right);
  avl = right;
  return avl;
}
static Avl* minV(Avl* avl){
  while(avl->left != NULL)
    avl = avl->left;
  return avl;

}
static Avl* Balance(Avl* avl){
  avl->height = max(height(avl->left), height(avl->right)) + 1;
  int balance = height(avl->left) - height(avl->right);
  int Lbalance;
  int Rbalance;
  if(avl->left == NULL)
    Lbalance = 0;
  else
  Lbalance = height(avl->left->left) - height(avl->left->right);
  if(avl->right == NULL)
    Rbalance = 0;
  else
    Rbalance = height(avl->right->left) - height(avl->right->left);
  if (balance > 1 && Lbalance >= 0){
    avl =  rightRotate(avl);
    return avl;
  }
    if (balance > 1 && Lbalance < 0)
    {
      avl -> left =  leftRotate(avl->left);
      avl =  rightRotate(avl);
      return avl ;
    }
    if (balance < -1 && Rbalance <= 0){
      avl =  leftRotate(avl);
      return avl;
    }
    if (balance < -1 && Rbalance  > 0)
    {
      avl->right=  rightRotate(avl->right);
      avl=  leftRotate(avl);
      return avl;
    }
    return avl;
}
Avl* AvlDelete(Avl* avl, int value){
  if(avl == NULL)
    return NULL;
  if(value  > avl->value)
    avl-> right = AvlDelete(avl->right,value);
  else
    if(value < avl->value)
      avl->left =  AvlDelete(avl->left,value);
    else
      if(avl->left == NULL & avl->right == NULL){
	free(avl);
	avl = NULL;
      }
      else
	if(avl->left == NULL && avl->right != NULL){
	  Avl* tmp = avl->right;
	  avl->value = avl->right->value;
	  avl->right = NULL;
	  free(tmp);
	}
	else
	  if(avl->left != NULL && avl->right == NULL){
	    Avl* tmp = avl->left;
	    avl-> value = avl->left->value;
            avl->left = NULL;
	    free(tmp);
	  }
	  else
	    if(avl->left != NULL && avl->right != NULL){
	      Avl* tmp = minV(avl->right);
	      avl->value = tmp->value;
	      AvlDelete(avl->right,tmp->value);
	    }
  if(avl == NULL)
    return NULL;
 avl = Balance(avl);
 avl->nChild = nChildCur(avl);
 return avl;
}

Avl* AvlInsert(Avl* avl, int value){
  if(avl  == NULL){
     avl = AvlNew(avl,value);
     return avl;
  }
    if (value < avl->value)
      avl->left=AvlInsert(avl->left,value);
    if(value > avl-> value)
      avl->right = AvlInsert(avl->right, value);
    if(value == avl->value)
      return avl;
    avl = Balance(avl);
    avl->nChild = nChildCur(avl);
    return avl;
}

void preOrder(Avl* avl){
  if(avl != NULL){
    printf("%d  ", avl->value);
    preOrder(avl->right);
    preOrder(avl->left);
  }

}
int main(){
  Avl* avl = NULL;
  int num;
  scanf("%d", &num);
  int i;

  for(i=0; i< num; i++){
    char type;
    char space;
    int number;
    scanf("%c",&space);
    scanf("%c %d",&type,&number);
    switch(type){
    case 'I':{
      printf("I qna\n");
      avl =  AvlInsert(avl,number);
      break;
    }
    case 'D':{
      printf("D qna\n");
      avl = AvlDelete(avl,number);
      break;
    }
    case 'K':{
      printf("K qna\n");
      // KIndex(avl,number);
      printf("   %d -- " , avl->left->height - avl->right->height);
      break;
    }
    case 'C':{
      printf("C qna\n");
      KLess(avl,number);
      break;
    }
    default:{
      printf("Error Type \n");
      break;
    }
    }
  }
  preOrder(avl);
  return 0;
}