class Node:
    def __init__(self, info):
        self.info = info  
        self.left = None  
        self.right = None 
        self.level = None 

    def __str__(self):
        return str(self.info) 
def height(root):
    if root is None:
        return 0
    return max(1+height(root.left),1+height(root.right))
def inOrder(root):
    if root == None:
        return
    inOrder(root.left)
    print (str(root.info)+'(BF='+str(height(root.left)-height(root.right))+')', end=" ")
    inOrder(root.right)
def preOrder(root):
    if root == None:
        return
    print (str(root.info)+'(BF='+str(height(root.left)-height(root.right))+')', end=" ")
    preOrder(root.left)
    preOrder(root.right)
def turnRight(t):
    x=t.left
    y=x.right
    t.left=y
    x.right = t
    return x
def turnLeft(t):
    x=t.right
    y=x.left
    t.right=y
    x.left = t
    return x
def swap(root):
    root.ht = height(root.left) - height(root.right)

    if root.ht > 1:
        if root.left:
            rlt = height(root.left.left) - height(root.left.right)
            if rlt < 0:
                root.left = turnLeft(root.left)
        return turnRight(root)

    if root.ht < -1:
        if root.right:
            rrt = height(root.right.left) - height(root.right.right)
            if rrt > 0:
                root.right = turnRight(root.right)
        return turnLeft(root)

    return root
class BinarySearchTree:
    def __init__(self): 
        self.root = None

#Node is defined as
#self.left (the left child of the node)
#self.right (the right child of the node)
#self.info (the value of the node)

    def insert(self, val):
        #Enter you code here.
        def _insert(root, val):
            if root is None:
                return Node(val)
            if val<root.info:
                root.left = _insert(root.left,val)
            if val>root.info:
                root.right=_insert(root.right,val)
            return swap(root)
        self.root = _insert(self.root,val)
tree = BinarySearchTree()
t = int(input())
arr = list(map(int, input().split()))
k=int(input())
arr.append(k)
for i in range(t+1):
    tree.insert(arr[i])
inOrder(tree.root)
print()
preOrder(tree.root)