class Node:
    def __init__(self,x):
        self.data = x
        self.count = 1
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    if node.data == x:
        node.count += 1
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is None:
        if node.count > 1:
            node.count -= 1
        else:
            return node.right
    else:
        node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.count > 1:
                node.count -= 1
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node
