import sys

lines = []

for line in sys.stdin:
    if "Exit" == line.rstrip():
        break
    lines.append(line.split("\n")[0])

nol = lines[0]
treeInput = [int(x) for x in lines[1].split(" ")]
toIns = lines[2]

# print(nol)
# print(treeInput)
# print(toIns)

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1  # Initially, new nodes have height 1

class AVLTree:
    def __init__(self):
        self.root = None

    def get_height(self, node):
        return node.height if node else 0
    
    def calculate_height(self, node):
        return 1 + max(self.get_height(node.left), self.get_height(node.right))
        
    def getBalance(self, node):
        return self.get_height(node.left) - self.get_height(node.right)

    # Insertion operation - Add your code here
    def insert(self, data):
        self.root = self._insert(self.root, data)

    def _insert(self, node, data):
        if not node:
            return Node(data)

        if data < node.data:
            node.left = self._insert(node.left, data)
        elif data > node.data:
            node.right = self._insert(node.right, data)
        else:
            return
        
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

        bf = self.getBalance(node)

        # An assignment / return statement is needed because, when applying the rotations, the structure of the currennt node's subtree will change, pointing to the new corresponding newly "generated" subrtree.
        ## LL rotation
        if bf > 1 and data < node.left.data:
            return self.rotate_right(node)
        ## LR rotation
        if bf > 1 and data > node.left.data:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        ## RR rotation
        if bf < -1 and data > node.right.data:
            return self.rotate_left(node)
        ## RL rotation
        if bf < -1 and data < node.right.data:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)
        
        # A return statement is needed because, when applying the rotations, the structure of the currennt node's subtree will change, pointing to the new corresponding newly "generated" subrtree.
        return node
          
    # A return statement is needed because, when applying a rotation, the structure of the currennt node's subtree will change, pointing to the new corresponding newly "generated" subrtree.
    def rotate_right(self, node):
        left = node.left
        left_right = left.right

        left.right = node
        node.left = left_right

        node.height = self.calculate_height(node)
        left.height = self.calculate_height(left)

        return left
    
    def rotate_left(self, node):
        right = node.right
        right_left = right.left

        right.left = node
        node.right = right_left

        node.height = self.calculate_height(node)
        right.height = self.calculate_height(right)

        return right

    # Traversals
    def inorder(self, node):
        if node is not None:
            self.inorder(node.left)
            print(f"{node.data}(BF={self.getBalance(node)})", end=" ")
            self.inorder(node.right)

    def postorder(self, node):
        if node is not None:
            print(f"{node.data}(BF={self.getBalance(node)})", end=" ")
            self.postorder(node.left)
            self.postorder(node.right)

    # Function to print BF at each node
    def print_balance(self):
        self.inorder(self.root)
        print("")
        self.postorder(self.root)

tree = AVLTree()
for x in treeInput:
    tree.insert(x)
tree.insert(int(toIns))
tree.print_balance()