#include <stdlib.h>
#include <stdio.h>
typedef struct node
{
    int k;
    struct node *l,*r;
}BT;

BT* INSBT(BT *root,BT *new_T)
{
    BT *p = root;
    if(root==NULL) 
        root=new_T;
    else
        while(p->k!=new_T->k)
            if(p->k<new_T->k)
                if(p->r==NULL) {
                    p->r=new_T;
                    break;
                }
                else 
                    p=p->r;
            else
                if(p->l==NULL) {
                    p->l=new_T;
                    break;
                }
    else p=p->l;
    return root;
}

BT* CREABT(int n)
{
    BT *root,*new_T;
    int i,key;
    for(root=NULL,i=1;i<=n;i++)
    {
        scanf("%d",&key);
        new_T=(BT*)malloc(sizeof(BT));
        new_T->k=key;
        new_T->l=new_T->r=NULL;
        root=INSBT(root,new_T);
    }
    return root;
}

BT* SEARBT(BT *root,int key)
{
    BT *p;
    for(p=root;p!=NULL&&p->k!=key;)
        if(p->k<key) 
            p=p->r;
        else p=p->l;
    return p;
}


BT* DELBT(BT *root, int key)
{                                // 删除key 
    BT *p,*q,*f;
    for(q=NULL,p=root;p!=NULL&&p->k!=key;)        // 遍历找到key 
    {
        q=p;                                    // p 是父节点，q是当前节点 
        if(key<p->k) 
            p=p->l;
        else 
            p=p->r;
    }
    if(p->k==key)
    {
        if(p->l==NULL)
            if(q->l==p)     
                q->l=p->r;else q->r=p->r;        // p父节点左子树为空，
        else
        {                                        // p父节点左子树不为空
            f=p;
            for(;p->r!=NULL;q=p,p=p->r);        // 沿着左子树的右孩子，右到底  
                f->k=p->k;
            q->r=p->l;                            // 将得到最右边的节点连接到q节点的左子树 
        }
        free(p);
    }
    return root;
}

void INBT(BT *root)
{
    if(root!=NULL)
    {
        INBT(root->l);
        printf("%d ",root->k);
        INBT(root->r);
    } 
}


int main()
{
    BT *root,*p;int n,key;
    scanf("%d",&n);
    root=CREABT(n);
    INBT(root);
    scanf("%d",&key);
    p=SEARBT(root,key);
    if(p==NULL) printf("\nno exit");
    else printf("\n%d",p->k);
    root=DELBT(root,key);
    printf("\n");
    INBT(root);
    return 0;
}