import random

class Node:
    def __init__(self, key, level):
        self.key = key
        # Initialize forward pointers to None for the given level
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, maxLevel):
        self.maxLevel = maxLevel
        self.level = 0  # Start with the lowest level
        self.header = Node(-1, maxLevel)  # Create a header node with a key of -1

    def randomLevel(self):
        lvl = 0
        # Randomly generate the level for the node
        while random.randint(0, 1) == 1 and lvl < self.maxLevel:
            lvl += 1
        return lvl

    def createNode(self, key, level):
        # A wrapper to create a new node
        return Node(key, level)

    def insertElement(self, key):
        update = [None] * (self.maxLevel + 1)
        current = self.header

        # Find the position to insert the new node
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current

        current = current.forward[0]

        # Insert the node if it is not present
        if current is None or current.key != key:
            rlevel = self.randomLevel()

            if rlevel > self.level:
                for i in range(self.level + 1, rlevel + 1):
                    update[i] = self.header
                self.level = rlevel

            n = self.createNode(key, rlevel)

            for i in range(rlevel + 1):
                n.forward[i] = update[i].forward[i]
                update[i].forward[i] = n
            print(f"Successfully inserted key {key}")

    def searchElement(self, key):
        current = self.header
        # Search for the key
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
        current = current.forward[0]

        if current and current.key == key:
            print(f"Found key: {key}")
            return True
        print(f"Key not found: {key}")
        return False

    def deleteElement(self, key):
        update = [None] * (self.maxLevel + 1)
        current = self.header

        # Find the node to be deleted
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current

        current = current.forward[0]

        if current is not None and current.key == key:
            # Delete the node
            for i in range(self.level + 1):
                if update[i].forward[i] != current:
                    break
                update[i].forward[i] = current.forward[i]

            while self.level > 0 and self.header.forward[self.level] is None:
                self.level -= 1
            print(f"Successfully deleted key {key}")

    def displayList(self):
        print("\n*****Skip List*****")
        for i in range(self.level + 1):
            print(f"Level {i}: ", end="")
            node = self.header.forward[i]
            while node:
                print(node.key, end=" ")
                node = node.forward[i]
            print("")

# Example usage
if __name__ == "__main__":
    lst = SkipList(10)

    # Insert elements
    for key in [3, 6, 7, 9, 12, 19, 17]:
        lst.insertElement(key)

    lst.displayList()

    # Search for an element
    lst.searchElement(6)

    # Delete an element
    lst.deleteElement(6)

    # Display list after deletion
    lst.displayList()