Design a Skiplist without using any built-in libraries.
A Skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists are just simple linked lists.
For example: we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way:

Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons
You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add , erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n).
To be specific, your design should include these functions:

bool search(int target) : Return whether the target exists in the Skiplist or not.
void add(int num): Insert a value into the SkipList. 
bool erase(int num): Remove a value in the Skiplist. If num does not exist in the Skiplist, do nothing and return false. If there exists multiple num values, removing any one of them is fine.

See more about Skiplist : https://en.wikipedia.org/wiki/Skip_list
Note that duplicates may exist in the Skiplist, your code needs to handle this situation.
 
Example:
Skiplist skiplist = new Skiplist();

skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   // return false.
skiplist.add(4);
skiplist.search(1);   // return true.
skiplist.erase(0);    // return false, 0 is not in skiplist.
skiplist.erase(1);    // return true.
skiplist.search(1);   // return false, 1 has already been erased.
 
Constraints:

0 <= num, target <= 20000
At most 50000 calls will be made to search, add, and erase.

Difficulty: interview

Starter code:

class Skiplist:
    def __init__(self):
    def search(self, target: int) -> bool:
    def add(self, num: int) -> None:
    def erase(self, num: int) -> bool:
# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

Solutions:
class Skiplist:
    def __init__(self):
        self.skip_list={}
        

    def search(self, target: int) -> bool:
        if(target in self.skip_list):
            if(self.skip_list[target]>0):
                return True
        return False
        

    def add(self, num: int) -> None:
        if(num in self.skip_list):
            self.skip_list[num]+=1
        else:
            self.skip_list[num]=1
        

    def erase(self, num: int) -> bool:
        if(num in self.skip_list):
            if(self.skip_list[num]>0):
                self.skip_list[num]-=1
                return True
        return False

class Node:
    def __init__(self, value=None, next=None, down=None):
        self.value = value
        self.next = next
        self.down = down
    
        
class Skiplist:

    def __init__(self):
        self.dict1 = dict()

    def search(self, target: int) -> bool:
        return target in list(self.dict1.keys())

    def add(self, num: int) -> None:
        self.dict1[num] = self.dict1.get(num, 0) + 1
        

    def erase(self, num: int) -> bool:
        if(num in list(self.dict1.keys())):
            self.dict1[num] -= 1
            if(self.dict1[num] == 0):
                del self.dict1[num]
            return True
        return False


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node:
    __slots__ = 'val', 'levels'
    def __init__(self, val, levels):
        self.val = val
        self.levels = [None] * levels

class Skiplist(object):
    def __init__(self):
        self.head = Node(-1, 16) 
    
    def _iter(self, num):
        cur = self.head
        for level in range(15, -1, -1):
            while True:
                future = cur.levels[level]
                if future and future.val < num:
                    cur = future
                else:
                    break
            yield cur, level

    def search(self, target):
        for prev, level in self._iter(target):
            pass
        cur = prev.levels[0]
        return cur and cur.val == target

    def add(self, num):
        nodelvls = min(16, 1 + int(math.log2(1.0 / random.random())))
        node = Node(num, nodelvls)
        
        for cur, level in self._iter(num):
            if level < nodelvls:
                future = cur.levels[level]
                cur.levels[level] = node
                node.levels[level] = future

    def erase(self, num):
        ans = False
        for cur, level in self._iter(num):
            future = cur.levels[level]
            if future and future.val == num:
                ans = True
                cur.levels[level] = future.levels[level]
        return ans

class Node(object):
    
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None

class Skiplist(object):

    def __init__(self):
        self.S = [Node(None)]

    def search(self, target):
        \"\"\"
        :type target: int
        :rtype: bool
        \"\"\"
        curr = self.S[-1]
        while curr:
            # Move right as far as possible without overshooting in the current level 
            while (curr.next is not None) and (curr.next.val <= target):
                if curr.next.val == target:
                    # If target found in some (potentially intermediate) level, exit immediately
                    return True
                curr = curr.next
            # Traversed current level as far as possible without finding target
            # Move one level down to expand search
            curr = curr.down
        # Traversed till the end without finding the target, return False
        return False

    def add(self, num):
        \"\"\"
        :type num: int
        :rtype: None
        \"\"\"
        # Start at the lowest level and keep flipping coins to decide whether
        # to insert an entry for the given value at the next higher level as well.
        k = 1
        p = random.choice([0, 1])
        while (p == 1) and (k < len(self.S)):
            k += 1
            p = random.choice([0, 1])
        if k == len(self.S):
            # If an entry will be inserted at the highest level, expand the number of levels.
            nr = Node(None)
            nr.down = self.S[-1]
            self.S.append(nr)
        curr = self.S[-1]
        kc = len(self.S)
        par = None
        while curr:
            # Traverse to the right in the current level as far as possible without overshooting.
            while (curr.next is not None) and (curr.next.val <= num):
                curr = curr.next
            if kc <= k:
                # An entry for the new value needs to be inserted in the current level.
                # This entry should be inserted just after the point where rightward traversal stopped.
                nn = Node(num)
                nn.next = curr.next
                curr.next = nn
                # Update the downward link for the new entry inserted in the previous level.
                if par is not None:
                    par.down = nn
                par = nn
            # Current level done, keep going down.
            curr = curr.down
            kc -= 1

    def erase(self, num):
        \"\"\"
        :type num: int
        :rtype: bool
        \"\"\"
        curr = self.S[-1]
        res = False
        while curr:
            # Traverse to the right in the current level as far as possible without overshooting.
            while (curr.next is not None) and (curr.next.val <= num):
                if curr.next.val == num:
                    # Target value found inside the next node in the current level.
                    # Delete the next node, and since we're done with the current level now,
                    # break out of the loop and move on to the next level downwards.
                    res = True
                    curr.next = curr.next.next
                    break
                else:
                    curr = curr.next
            # Go one level down and repeat the process.
            curr = curr.down
        # Trim the levels if multiple levels can be found towards the top which have only the dummy terminal entry.
        # Leave only one of them.
        while len(self.S) >= 2:
            cand = self.S[-2]
            if cand.next is None:
                self.S.pop()
            else:
                break
        return res
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

class Node:
    def __init__(self,val):
        self.val=val        # value of the node
        self.next=None      # have next node
        self.down=None      # have down node

class Skiplist:
    def __init__(self):
        self.levels=[]                    # define the levels
        prev=None                         # have previous node reference
        for i in range(16):               # 16 levels to cover the calls
            node=Node(-math.inf)          # initialize node to - infinity
            self.levels.append(node)      # append to the list growing vertically
            if prev:
                prev.down=node            # populate the down node
            prev=node                     # populate the current node as previous 
            
    def _iter(self,val):
        res=[]                                # list for the results
        l=self.levels[0]                      # start from 0th level
        while l:                              # loop from level 0 and move vertically down
            while l.next and l.next.val<val:  # as we visit each node, check if the value is lesser
                l=l.next                      # move horizontally next
            res.append(l)                     # append to the results
            l=l.down                          # move vertically down
        return res                            # return the result
        
    def search(self, target: int) -> bool:
        last=self._iter(target)[-1]                    # get the last element in the result after traversing for target
        return last.next and last.next.val==target     # return the element if it matches 
        
    def add(self, num: int) -> None:
        res=self._iter(num)                            # get result as the position for num to add
        prev=None                                      # previous is None to start with
        for i in range(len(res)-1,-1,-1):              # move from top to bottom level
            node=Node(num)                             # create Node for the value
            node.next,node.down=res[i].next,prev       # assign the next value and down value 
            res[i].next=prev=node                      # assign the node to next and previous
            rand=random.random()                       # randomly decide to skip or not in each of the level 
            if rand>0.5:
                break
                
    def erase(self, num: int) -> bool:
        found=False                                      # found is false initially
        res=self._iter(num)                              # get the result for the number
        for i in range(len(res)):                        # iterate through the length of the results
            if res[i].next and res[i].next.val==num:     # if the value matches with levels next val
                res[i].next=res[i].next.next             # then skip the node and point to next next node
                found=True                               # set flag and return
        return found

class Node(object):
    
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None

class Skiplist(object):

    def __init__(self):
        self.S = [Node(None)]

    def search(self, target):
        \"\"\"
        :type target: int
        :rtype: bool
        \"\"\"
        curr = self.S[-1]
        while curr:
            # Move right as far as possible without overshooting in the current level 
            while curr.next and (curr.next.val <= target):
                if curr.next.val == target:
                    # If target found in some (potentially intermediate) level, exit immediately
                    return True
                curr = curr.next
            # Traversed current level as far as possible without finding target
            # Move one level down to expand search
            curr = curr.down
        # Traversed till the end without finding the target, return False
        return False

    def add(self, num):
        \"\"\"
        :type num: int
        :rtype: None
        \"\"\"
        # Start at the lowest level and keep flipping coins to decide whether
        # to insert an entry for the given value at the next higher level as well.
        k = 1
        p = random.choice([0, 1])
        while (p == 1) and (k < len(self.S)):
            k += 1
            p = random.choice([0, 1])
        if k == len(self.S):
            # If an entry will be inserted at the highest level, expand the number of levels.
            nr = Node(None)
            nr.down = self.S[-1]
            self.S.append(nr)
        curr = self.S[-1]
        kc = len(self.S)
        par = None
        while curr:
            # Traverse to the right in the current level as far as possible without overshooting.
            while curr.next and (curr.next.val <= num):
                curr = curr.next
            if kc <= k:
                # An entry for the new value needs to be inserted in the current level.
                # This entry should be inserted just after the point where rightward traversal stopped.
                nn = Node(num)
                nn.next = curr.next
                curr.next = nn
                # Update the downward link for the new entry inserted in the previous level.
                if par is not None:
                    par.down = nn
                par = nn
            # Current level done, keep going down.
            curr = curr.down
            kc -= 1

    def erase(self, num):
        \"\"\"
        :type num: int
        :rtype: bool
        \"\"\"
        curr = self.S[-1]
        res = False
        while curr:
            # Traverse to the right in the current level as far as possible without overshooting.
            while curr.next and (curr.next.val <= num):
                if curr.next.val == num:
                    # Target value found inside the next node in the current level.
                    # Delete the next node, and since we're done with the current level now,
                    # break out of the loop and move on to the next level downwards.
                    res = True
                    curr.next = curr.next.next
                    break
                else:
                    curr = curr.next
            # Go one level down and repeat the process.
            curr = curr.down
        # Trim the levels if multiple levels can be found towards the top which have only the dummy terminal entry.
        # Leave only one of them.
        while len(self.S) >= 2:
            cand = self.S[-2]
            if cand.next is None:
                self.S.pop()
            else:
                break
        return res
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

import math
import random

class Node:
    def __init__(self, val):
        self.next = None
        self.prev = None
        self.down = None
        self.val = val
    
class Skiplist:

    def __init__(self):
        self.lvls = math.ceil(math.log(50000)/math.log(2))
        self.topleft = self.add_first(-1<<31) 

    def search_(self, target: int):
        x = self.topleft
        out = []
        while True: 
            while x.__next__ and x.next.val <= target:
                x = x.__next__
            out.append(x)
            if x.down:
                x = x.down
            else:
                break
        return out
   
    def ll_to_list(self,x):
        out = []
        while x:
            out.append(x.val) 
            x = x.__next__
        return out
    
    def print_lvls(self):
        x = self.topleft
        for i in range(self.lvls):
            print((self.ll_to_list(x)))
            x = x.down
        print()
    
    def search(self, target: int) -> bool:
        x = self.topleft 
        while True: 
            while x.__next__ and x.next.val <= target:
                x = x.__next__
            if x.down:
                x = x.down
            else:
                break
        if x and x.val == target: return True
        return False
    
    def insert(self, x, num):
        n = Node(num)
        p,q = x, x.__next__
        p.next = n
        n.prev = p
        n.next = q
        if q:
            q.prev = n
        return n
    
    def add_first(self, num):
        prev = None
        for i in range(self.lvls-1,-1,-1):
            n = Node(num)
            if prev:
                n.down = prev
            prev = n
        return prev 
        
    def add(self, num: int) -> None:
        xs = self.search_(num)
        prev = self.insert(xs[self.lvls-1],num)
        for i in range(self.lvls-2,-1,-1):
            if random.random() > 0.5:
                curr = self.insert(xs[i], num)
                if prev:
                    curr.down = prev
                prev = curr
            else:
                break
    
    def delete(self,x):
        p,q,r = x.prev, x, x.__next__
        p.next = r
        if r: 
            r.prev = p
        
    def erase(self, num: int) -> bool:
        xs = self.search_(num)
        prev = None
        found = False
        for i in range(self.lvls-1,-1,-1):
                if xs[i].val == num:
                    found = True
                    self.delete(xs[i])
                else:
                    break
        return found


class Node:
    def __init__(self, val, next = None, down = None):
        self.val = val
        self.next = next
        self.down = down
class Skiplist:
    # https://www.youtube.com/watch?v=1kF6W_9QNp8
    import random
    def __init__(self):
        self.heads = []
        self.level = 0

    def printList(self):
        res = []
        for head in self.heads:
            curr, l = head.__next__, []
            while curr:
                l.append(curr.val)
                curr = curr.__next__
            res.append(l)
        return res
                
    def search(self, target: int) -> bool:
        # print('search {0}'.format(target))
        curr = self.heads[-1]
        while curr:
            while curr.__next__ and curr.next.val < target:
                curr = curr.__next__
            # print('curr = {0}'.format(curr.val if curr else -1))
            if curr.__next__ and curr.next.val == target:
                return True
            curr = curr.down
        return False

    def add(self, num: int) -> None:
        # print('add {0}'.format(num))
        if not self.heads:
            head = Node(-1, Node(num, None, None), None)
            self.heads.append(head)
            self.level = 1
            # print('list = {0}'.format(self.printList()))
            return
        newLevel = 1
        while newLevel <= self.level and not random.randint(1, 100) & 1:
            newLevel += 1
        addNewLevel = False
        if newLevel > self.level:
            self.level = newLevel
            node = Node(num, None, None)
            head = Node(-1, node, self.heads[-1]) if self.heads else Node(-1, node, None)
            self.heads.append(head)
            addNewLevel = True
        if addNewLevel:
            if len(self.heads) == 1:
                return
            curr, prev = self.heads[-2], self.heads[-1].__next__
        else:
            curr, prev = self.heads[-1], None          
        # print('addNewLevel = {0}, curr = {1}, level = {2}, heads size = {3}, prev = {4}'.format(addNewLevel, curr.val, self.level, len(self.heads), -1 if not prev else prev.val))
        # print('newLevel = {0}'.format(newLevel))
        for i in range(self.level - 1 if addNewLevel else self.level, 0, -1):
            while curr.__next__ and curr.next.val < num:
                curr = curr.__next__
            if i <= newLevel:
                curr.next = Node(num, curr.next, None)
                if prev:
                    prev.down = curr.__next__
                prev = curr.__next__
            curr = curr.down
        # print('list = {0}'.format(self.printList()))

    def erase(self, num: int) -> bool:
        # print('erase {0}'.format(num))
        curr = self.heads[-1]
        seen = False
        for i in range(self.level):
            while curr.__next__ and curr.next.val < num:
                curr = curr.__next__
            if curr.__next__ and curr.next.val == num:
                seen = True
                tmp = curr.__next__
                curr.next = curr.next.__next__
                tmp = None
            curr = curr.down
        # print('erase {0}, list = {1}'.format(num, self.printList()))
        return seen
                


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node:
    def __init__(self,val):
        self.val=val
        self.next=None
        self.down=None

class Skiplist:
    def __init__(self):
        self.levels=[]
        prev=None
        for i in range(16):
            node=Node(-math.inf)
            self.levels.append(node)
            if prev:
                prev.down=node
            prev=node
\t\t\t
    def _iter(self,val):
        res=[]
        l=self.levels[0]
        while l:
            while l.next and l.next.val<val:
                l=l.next
            res.append(l)
            l=l.down
        return res
\t\t
    def search(self, target: int) -> bool:
        last=self._iter(target)[-1]
        return last.next and last.next.val==target
\t\t
    def add(self, num: int) -> None:
        res=self._iter(num)
        prev=None
        for i in range(len(res)-1,-1,-1):
            node=Node(num)
            node.next,node.down=res[i].next,prev
            res[i].next=prev=node
            rand=random.random()
            if rand>0.5:
                break
\t\t\t\t
    def erase(self, num: int) -> bool:
        found=False
        res=self._iter(num)
        for i in range(len(res)):
            if res[i].next and res[i].next.val==num:
                res[i].next=res[i].next.next
                found=True
        return found

class Node:
    def __init__(self, val, level):
        self.val = val
        self.levels = [None] * level

class Skiplist:

    def __init__(self):
        self.head = Node(-1, 16)
    
    def _iter(self, num):
        cur = self.head
        for level in range(15, -1, -1):
            while True:
                future = cur.levels[level]
                if future and future.val < num:
                    cur = future
                else:
                    break
            yield cur, level

    def search(self, target: int) -> bool:
        for prev,level in self._iter(target):
            pass
        cur = prev.levels[0]
        return cur and cur.val == target

    def add(self, num: int) -> None:
        nodelvls = min(16, 1 + int(math.log2(1.0/random.random())))
        node = Node(num, nodelvls)
        
        for cur, level in self._iter(num):
            if level < nodelvls:
                future = cur.levels[level]
                cur.levels[level] = node
                node.levels[level] = future

    def erase(self, num: int) -> bool:
        res = False
        for cur,level in self._iter(num):
            future = cur.levels[level]
            if future and future.val == num:
                res = True
                cur.levels[level] = future.levels[level]
        return res


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node:
    def __init__(self,val):
        self.val=val
        self.next=None
        self.down=None

        
class Skiplist:
    def __init__(self):
        self.levels=[]
        prev=None
        for i in range(16):
            node=Node(-math.inf)
            self.levels.append(node)
            if prev:
                prev.down=node
            prev=node
\t\t\t
    def _iter(self,val):
        res=[]
        l=self.levels[0]
        while l:
            while l.next and l.next.val<val:
                l=l.next
            res.append(l)
            l=l.down
        return res
\t\t
    def search(self, target: int) -> bool:
        last=self._iter(target)[-1]
        return last.next and last.next.val==target
\t\t
    def add(self, num: int) -> None:
        res=self._iter(num)
        prev=None
        for i in range(len(res)-1,-1,-1):
            node=Node(num)
            node.next,node.down=res[i].next,prev
            res[i].next=node
            prev=node
            rand=random.random()
            if rand>0.5:
                break
\t\t\t\t
    def erase(self, num: int) -> bool:
        found=False
        res=self._iter(num)
        for i in range(len(res)):
            if res[i].next and res[i].next.val==num:
                res[i].next=res[i].next.next
                found=True
        return found


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

import math
import random

class Node:
    def __init__(self, val):
        self.next = None
        self.prev = None
        self.down = None
        self.val = val
    
class Skiplist:

    def __init__(self):
        self.lvls = math.ceil(math.log(50000)/math.log(2))
        self.topleft = self.add_first(-1<<31) 

    def search_(self, target: int):
        x = self.topleft
        out = []
        while True: 
            while x.__next__ and x.next.val <= target:
                x = x.__next__
            out.append(x)
            if x.down:
                x = x.down
            else:
                break
        return out
   
    def ll_to_list(self,x):
        out = []
        while x:
            out.append(x.val) 
            x = x.__next__
        return out
    
    def print_lvls(self):
        x = self.topleft
        for i in range(self.lvls):
            print((self.ll_to_list(x)))
            x = x.down
        print()
    
    def search(self, target: int) -> bool:
        # self.print_lvls() 
        x = self.topleft 
        while True: 
            while x.__next__ and x.next.val <= target:
                x = x.__next__
            if x.down:
                x = x.down
            else:
                break
        if x and x.val == target: return True
        return False
    
    def insert(self, x, num):
        n = Node(num)
        p,q = x, x.__next__
        p.next = n
        n.prev = p
        n.next = q
        if q:
            q.prev = n
        return n
    
    def add_first(self, num):
        prev = None
        for i in range(self.lvls-1,-1,-1):
            n = Node(num)
            if prev:
                n.down = prev
            prev = n
        return prev 
        
    def add(self, num: int) -> None:
        xs = self.search_(num)
        prev = self.insert(xs[self.lvls-1],num)
        for i in range(self.lvls-2,-1,-1):
            if random.random() > 0.5:
                curr = self.insert(xs[i], num)
                if prev:
                    curr.down = prev
                prev = curr
            else:
                break
        # print(f\"Adding {num}\")
        # self.print_lvls()
    
    def delete(self,x):
        p,q,r = x.prev, x, x.__next__
        p.next = r
        if r: 
            r.prev = p
        
    def erase(self, num: int) -> bool:
        xs = self.search_(num)
        prev = None
        found = False
        for i in range(self.lvls-1,-1,-1):
                if xs[i].val == num:
                    found = True
                    self.delete(xs[i])
                else:
                    break
        return found

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Skiplist:

    def __init__(self):
        self.d = {}

    def search(self, target: int) -> bool:
        return bool(self.d.get(target, False))

    def add(self, num: int) -> None:
        self.d[num] = self.d.get(num, 0) + 1

    def erase(self, num: int) -> bool:
        result = self.search(num)
        if result:
            self.d[num] -= 1
        return result

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class SkipNode:
    def __init__(self, val=None, height=0):
        self.val = val
        self.count = 1
        self.next = [None]*height
        

class Skiplist:

    def __init__(self):
        self.head = SkipNode()
        self.height = 0
        
    def get_path(self, val):
        path = [None] * self.height
        current = self.head
        for index in reversed(list(range(self.height))):
            while current.next[index] is not None and current.next[index].val < val:
                current = current.next[index]
            path[index] = current
        return path
    
    def find(self, val, path=None):
        if path is None:
            path = self.get_path(val)
        if path:
            match = path[0].next[0]
            if match and match.val == val:
                return match
        return None
    
    def get_height(self):
        height = 1
        while randint(0,1) and height <= (2*self.height) + 1:
            height += 1
        return height
    
    def search(self, target: int) -> bool:
        path = self.get_path(target)
        node = self.find(target, path)
        return node is not None and node.val == target
        

    def add(self, num: int) -> None:
        new_node = SkipNode(num, self.get_height())
        self.height = max(self.height, len(new_node.__next__))
        while len(self.head.__next__) < len(new_node.__next__):
            self.head.next.append(None)
        path = self.get_path(num)
        node = self.find(num, path)
        if node is None:
            for i in range(len(new_node.__next__)):
                new_node.next[i], path[i].next[i] = path[i].next[i], new_node
        else:
            node.count += 1

    def erase(self, num: int) -> bool:
        path = self.get_path(num)
        node = self.find(num, path)
        if not node:
            return False
        
        if node.count == 1:
            for i in range(len(node.__next__) -1, -1, -1):
                path[i].next[i] = node.next[i]
                if self.head.next[i] == None:
                    self.height -= 1
        else:
            node.count -= 1
        return True


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node:
    def __init__(self, val):
        self.val = val
        self.prev = self.next = self.up = self.down = None

class Skiplist:

    def __init__(self):
        self.heads = []
        self.tails = []
        self.newLevel()
        
    def newLevel(self):
        head = Node(float(\"-inf\"))
        tail = Node(float(\"inf\"))
        self.link_prev_next(head, tail)
        if self.heads:
            self.link_up_down(head, self.heads[-1])
            self.link_up_down(tail, self.tails[-1])
        self.heads.append(head)
        self.tails.append(tail)
        
    def find(self, num):
        node = self.heads[-1]
        tails = []
        while node:
            while node.next and num > node.next.val:
                node = node.next
            tails.append(node)
            node = node.down
        return tails

    def search(self, target: int) -> bool:
        return target == self.find(target)[-1].next.val

    def add(self, num: int) -> None:
        tails = self.find(num)
        left = tails.pop()
        node = Node(num)
        self.insert(left, left.next, node)
        while random.random() <= 0.5:
            new_node = Node(num)
            self.link_up_down(new_node, node)
            if not tails:
                self.newLevel()
                left = self.heads[-1]
            else:
                left = tails.pop()
            self.insert(left, left.next, new_node)
            node = new_node

    def erase(self, num: int) -> bool:
        node = self.find(num)[-1].next
        if node.val != num:
            return False
        while node:
            self.link_prev_next(node.prev, node.next)
            node = node.up
        return True
    
    def link_prev_next(self, node1, node2):
        node1.next = node2
        node2.prev = node1
    
    def link_up_down(self, node1, node2):
        node1.down = node2
        node2.up = node1
        
    def insert(self, left, right, node):
        self.link_prev_next(left, node)
        self.link_prev_next(node, right)
            

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

class Node:
    def __init__(self, val):
        self.val = val
        self.next, self.down = None, None

class Skiplist:

    def __init__(self):
        self.levels = []
        prev = None
        for i in range(16):
            self.levels.append(Node(float('-inf')))
            if prev:
                prev.down = self.levels[-1]
            prev = self.levels[-1]
            
    def _iter(self, target):
        res = []
        node = self.levels[0]
        while node:
            while node.__next__ and node.next.val<target:
                node = node.__next__
            res.append(node)
            node = node.down
        return res

    def search(self, target: int) -> bool:
        found = self._iter(target)
        return found[-1].__next__ and found[-1].next.val==target

    def add(self, num: int) -> None:
        down = None
        for node in self._iter(num)[::-1]:
            new_node = Node(num)
            new_node.next = node.__next__
            new_node.down = down
            node.next = new_node
            if random.randint(0, 1)==1:
                return
            down = new_node

    def erase(self, num: int) -> bool:
        found = False
        for node in self._iter(num):
            if node.__next__ and node.next.val==num:
                node.next = node.next.__next__
                found = True
        
        return found


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node:
    def __init__(self, val):
        self.val = val
        self.next, self.lower = None, None
    
class Skiplist:

    def __init__(self):
        self.sentinel = Node(-sys.maxsize)
        self.overhead = Node(-sys.maxsize)
        self.overhead.lower = self.sentinel

    def _flip(self, cur):
        target = None if not cur.__next__ else cur.next.lower
        p, count = cur.lower, 0
        while p != target:
            p = p.__next__
            count += 1
        if count >= 4:
            lower = cur.lower.next.__next__
            new_node = Node(lower.val)
            new_node.next, new_node.lower = cur.__next__, lower
            cur.next = new_node
        
    def search(self, target: int) -> bool:
        cur = self.sentinel
        while cur:
            if cur.val == target:
                return True
            elif not cur.__next__ or cur.next.val > target:
                cur = cur.lower
            else:
                cur = cur.__next__
        return False

    def add(self, num: int) -> None:
        def insertLower(head):
            cur = head
            while cur.__next__ and cur.next.val <= num:
                cur = cur.__next__
            if cur.lower:
                insertLower(cur.lower)
                self._flip(cur)
            else:
                new_node = Node(num)
                new_node.next = cur.__next__
                cur.next = new_node
        insertLower(self.sentinel)
        count = 0
        p = self.sentinel
        while p:
            p = p.__next__
            count += 1
        if count >= 4:
            new_level = Node(-sys.maxsize)
            lower = self.sentinel.next.__next__
            new_node = Node(lower.val)
            new_node.lower = lower
            new_level.next = new_node
            new_level.lower = self.sentinel
            self.sentinel = new_level
    

    def erase(self, num: int) -> bool:
        def eraseLower(head):
            cur = head
            while cur.__next__ and cur.next.val < num:
                cur = cur.__next__
            removed = None
            if cur.lower:
                deleted = eraseLower(cur.lower)
                if cur.__next__ and cur.next.lower == deleted:
                    removed = cur.__next__
                    cur.next = cur.next.__next__
                self._flip(cur)
            else:
                removed = cur.__next__
                cur.next = cur.next.__next__
            return removed
        
        if not self.search(num):
            return False
        
        eraseLower(self.sentinel)
        while self.sentinel.lower and not self.sentinel.__next__:
            self.sentinel = sentinel.lower
        return True


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None
        
    def __str__(self):
        print((self.val))

class Skiplist:

    def __init__(self):
        self.heads = [Node(float('-inf')) for i in range(16)]
        self.tails = [Node(float('inf')) for i in range(16)]
        
        for i in range(16):
            self.heads[i].next = self.tails[i]
            
        for i in range(15):
            self.heads[i].down = self.heads[i+1]
        # for up, down in zip(self.heads, self.heads[1:]):
        #     up.down = down

    def search(self, target: int) -> bool:
        start = self.heads[0]
        while start:
            if start.next.val == target: return True
            elif start.val < target < start.next.val:
                start = start.down
            else:
                start = start.__next__
        return False
                

    def add(self, num: int) -> None:
        start = self.heads[0]
        stack = []
        while start:
            #print(start.val,start.next.val, start.id)
            if start.val < num <= start.next.val:
                stack.append(start)
                start = start.down
            else:
                start = start.__next__
                
        pre = None
        while stack:
            cur = stack.pop()
            newnode = Node(num)
            newnode.next = cur.__next__
            cur.next = newnode
            if pre:
                newnode.down = pre
            pre = newnode
            
            if random.randint(0, 1) == 1: break
            
        

    def erase(self, num: int) -> bool:
        if not self.search(num): return False
        start = self.heads[0]
        while start:
            if start.next.val == num: 
                # remove 
                start.next = start.next.__next__
                start = start.down
                
            elif start.val < num < start.next.val:
                start = start.down
            else:
                start = start.__next__
        return True


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node:
    def __init__(self, val):
        self.val = val
        self.right, self.down = None, None
        
class Skiplist:

    def __init__(self):
        self.head = [Node(float('-inf')) for _ in range(16)]
        self.tail = [Node(float('inf')) for _ in range(16)]
        
        for h, t in zip(self.head, self.tail):
            h.right = t
            
        for up, down in zip(self.head, self.head[1:]):
            up.down = down

    def search(self, target: int) -> bool:
        current = self.head[0]
        while current:
            if current.val < target <= current.right.val:
                if current.right.val == target: return True
                current = current.down
            else:
                current = current.right
        return False
        
    def add(self, num: int) -> None:
        stack = []
        current = self.head[0]
        while current:
            if current.val < num <= current.right.val:
                stack.append(current)
                current = current.down
            else:
                current = current.right
        prev = None
        while stack:
            current = stack.pop()
            node = Node(num)
            node.right, current.right = current.right, node
            if prev: node.down = prev
            prev = node
            
            if random.randint(0, 1): break
        

    def erase(self, num: int) -> bool:
        current = self.head[0]
        is_removed = False
        while current:
            if current.val < num <= current.right.val:
                if current.right.val == num: 
                    current.right = current.right.right
                    is_removed = True
                current = current.down
            else:
                current = current.right
        return is_removed


class Node:
    def __init__(self, val, id):
        self.val = val
        self.id = id
        self.next = None
        self.down = None

class Skiplist:

    def __init__(self):
        self.heads = [Node(float('-inf'), i) for i in range(16)]
        self.tails = [Node(float('inf'), i) for i in range(16)]
        
        for i in range(16):
            self.heads[i].next = self.tails[i]
            
        for i in range(15):
            self.heads[i].down = self.heads[i+1]
        # for up, down in zip(self.heads, self.heads[1:]):
        #     up.down = down

    def search(self, target: int) -> bool:
        start = self.heads[0]
        while start:
            if start.next.val == target: return True
            elif start.val < target < start.next.val:
                start = start.down
            else:
                start = start.__next__
        return False
                

    def add(self, num: int) -> None:
        start = self.heads[0]
        stack = []
        while start:
            #print(start.val,start.next.val, start.id)
            if start.val < num <= start.next.val:
                stack.append(start)
                start = start.down
            else:
                start = start.__next__
                
        pre = None
        while stack:
            cur = stack.pop()
            newnode = Node(num, 0)
            newnode.next = cur.__next__
            cur.next = newnode
            if pre:
                newnode.down = pre
            pre = newnode
            
            if random.randint(0, 1) == 1: break
            
        

    def erase(self, num: int) -> bool:
        if not self.search(num): return False
        start = self.heads[0]
        while start:
            if start.next.val == num: 
                # remove 
                start.next = start.next.__next__
                start = start.down
                
            elif start.val < num < start.next.val:
                start = start.down
            else:
                start = start.__next__
        return True


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


import random

class Node:
  def __init__(self, val, level, count = 1):
    self.val = val
    # list hold refr to nodes on different level
    self.next = [None] * (level + 1)
    # count the number of duplicates of this val
    self.count = count

class Skiplist:

  def __init__(self, p = 0.5):
    # promote probability
    self.p = p
    # head of the skiplist
    self.head = Node(None, 0)
    # num of levels of the skiplist
    self.levels = 1

  def _randomLevel(self):
    # generate a random level
    _level = 0
    while random.random() < self.p:
      _level += 1
    return _level
  
  def _update(self, val):
    # candidate list of node to be updated at each level
    update = [None] * self.levels
    x = self.head
    for i in reversed(range(self.levels)):
      while x.next[i] is not None and x.next[i].val < val:
        x = x.next[i]
      update[i] = x
    return update
  
  def _search(self, val, update = None):
    if update is None:
      update = self._update(val)
    if len(update) > 0:
      node = update[0].next[0]
      if node is not None and node.val == val:
        return node
    return None

  def _insert(self, val: int) -> None:
    # node with val already exist?
    node = self._search(val)
    if node is not None:
      node.count += 1
    else:
      # node creation
      node = Node(val, self._randomLevel())
      # update max level and extend head correspondingly
      self.levels = max(self.levels, len(node.next))
      while len(self.head.next) < len(node.next):
        self.head.next.append(None)
      # update list of candidates
      update = self._update(val)
      for i in range(len(node.next)):
        node.next[i] = update[i].next[i]
        update[i].next[i] = node
    return None

  def _delete(self, val: int) -> bool:
    update = self._update(val)
    node = self._search(val, update)
    if node is not None:
      node.count -= 1
      if node.count < 1:
        for i in reversed(range(len(node.next))):
          update[i].next[i] = node.next[i]
          if self.head.next[i] is None:
            self.head.next.pop()
            self.levels -= 1
      return True
    else:
      return False

  def display(self) -> None:
    for i in range(len(self.head.next) - 1, -1, -1):
      x, s = self.head, ''
      while x.next[i] != None:
        s += str(x.next[i].val) + '(' + str(x.next[i].count) + ') -- '
        x = x.next[i]
      print('level', '{:4d}'.format(i), ':',  s)

  def search(self, target: int) -> bool:
    return self._search(target) is not None

  def add(self, num: int) -> None:
    return self._insert(num)

  def erase(self, num: int) -> bool:
    return self._delete(num)

class LinkedList:
    
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None


class Skiplist:

    def __init__(self):
        self.levels = [LinkedList(-1) for _ in range(20)]
        for u, d in zip(self.levels[:-1], self.levels[1:]):
            u.down = d

    def search(self, target: int) -> bool:
        pointer = self.levels[0]
        while pointer:
            if pointer.__next__ != None and pointer.next.val < target:
                pointer = pointer.__next__
            elif pointer.__next__ != None and pointer.next.val == target:
                return True
            else:
                pointer = pointer.down
        return False

    def add(self, num: int) -> None:
        stack = []
        pre = None
        pointer = self.levels[0]
        
        while pointer:
            if pointer.__next__ != None and pointer.next.val <= num:
                pointer = pointer.__next__
            else:#if pointer.next != None and pointer.next.val > target:
                stack.append(pointer)
                pointer = pointer.down
        while stack:
            pointer = stack.pop(-1)
            newNode = LinkedList(num)
            newNode.next, pointer.next = pointer.next, newNode
            if pre:
                newNode.down = pre
            pre = newNode
            if random.randrange(2): break

    def erase(self, num: int) -> bool:
        found = False
        pointer = self.levels[0]
        while pointer:
            if pointer.__next__ != None and pointer.next.val < num:
                pointer = pointer.__next__
            elif pointer.__next__ != None and pointer.next.val == num:
                pointer.next = pointer.next.__next__
                found = True
                pointer = pointer.down
            else:
                pointer = pointer.down
        return found


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


import random

class Node:
  def __init__(self, val, level, count = 1):
    self.val = val
    # list hold refr to nodes on different level
    self.next = [None] * (level + 1)
    # count the number of duplicates of this val
    self.count = count

class Skiplist:

  def __init__(self, p = 0.5):
    # promote probability
    self.p = p
    # head of the skiplist
    self.head = Node(None, 0)
    # num of levels of the skiplist
    self.levels = 1

  def _randomLevel(self):
    # generate a random level
    _level = 0
    while random.random() < self.p:
      _level += 1
    return _level
  
  def _update(self, val):
    # candidate list of node to be updated at each level
    update = [None] * self.levels
    x = self.head
    for i in reversed(list(range(self.levels))):
      while x.next[i] is not None and x.next[i].val < val:
        x = x.next[i]
      update[i] = x
    return update
  
  def _search(self, val, update = None):
    if update is None:
      update = self._update(val)
    if len(update) > 0:
      node = update[0].next[0]
      if node is not None and node.val == val:
        return node
    return None

  def _insert(self, val: int) -> None:
    # node with val already exist?
    node = self._search(val)
    if node is not None:
      node.count += 1
    else:
      # node creation
      node = Node(val, self._randomLevel())
      # update max level and extend head correspondingly
      self.levels = max(self.levels, len(node.__next__))
      while len(self.head.__next__) < len(node.__next__):
        self.head.next.append(None)
      # update list of candidates
      update = self._update(val)
      for i in range(len(node.__next__)):
        node.next[i] = update[i].next[i]
        update[i].next[i] = node
    return None

  def _delete(self, val: int) -> bool:
    update = self._update(val)
    node = self._search(val, update)
    if node is not None:
      node.count -= 1
      if node.count < 1:
        for i in reversed(list(range(len(node.__next__)))):
          update[i].next[i] = node.next[i]
          if self.head.next[i] is None:
            self.head.next.pop()
            self.levels -= 1
      return True
    else:
      return False

  def display(self) -> None:
    for i in range(len(self.head.__next__) - 1, -1, -1):
      x, s = self.head, ''
      while x.next[i] != None:
        s += str(x.next[i].val) + '(' + str(x.next[i].count) + ') -- '
        x = x.next[i]
      print(('level', '{:4d}'.format(i), ':',  s))

  def search(self, target: int) -> bool:
    return self._search(target) is not None

  def add(self, num: int) -> None:
    return self._insert(num)

  def erase(self, num: int) -> bool:
    return self._delete(num)

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Skiplist:

    def __init__(self):
        self.skip_list={}
        

    def search(self, target: int) -> bool:
        if(target in self.skip_list):
            if(self.skip_list[target]>0):
                return True
        return False
        

    def add(self, num: int) -> None:
        if(num in self.skip_list):
            self.skip_list[num]+=1
        else:
            self.skip_list[num]=1
        

    def erase(self, num: int) -> bool:
        if(num in self.skip_list):
            if(self.skip_list[num]>0):
                self.skip_list[num]-=1
                return True
        return False

import random

class Node:
  def __init__(self, val, level, count = 1):
    self.val = val
    # list hold refr to nodes on different level
    self.next = [None] * (level + 1)
    # count the number of duplicates of this val
    self.count = count

class Skiplist:

  def __init__(self, p = 0.5):
    # promote probability
    self.p = p
    # head of the skiplist
    self.head = Node(None, 0)
    # num of levels of the skiplist
    self.levels = 1

  def _randomLevel(self):
    # generate a random level
    _level = 0
    while random.random() < self.p:
      _level += 1
    return _level
  
  def _update(self, val):
    # candidate list of node to be updated at each level
    update = [None] * self.levels
    x = self.head
    for i in reversed(range(self.levels)):
      while x.next[i] is not None and x.next[i].val < val:
        x = x.next[i]
      update[i] = x
    return update
  
  def _search(self, val, update = None):
    if update is None:
      update = self._update(val)
    if len(update) > 0:
      node = update[0].next[0]
      if node is not None and node.val == val:
        return node
    return None

  def _insert(self, val: int) -> None:
    # node with val already exist?
    node = self._search(val)
    if node is not None:
      node.count += 1
    else:
      # node creation
      node = Node(val, self._randomLevel())
      # update max level and extend head correspondingly
      self.levels = max(self.levels, len(node.next))
      while len(self.head.next) < len(node.next):
        self.head.next.append(None)
      # update list of candidates
      update = self._update(val)
      for i in range(len(node.next)):
        node.next[i] = update[i].next[i]
        update[i].next[i] = node
    return None

  def _delete(self, val: int) -> bool:
    update = self._update(val)
    node = self._search(val, update)
    if node is not None:
      node.count -= 1
      if node.count < 1:
        for i in reversed(range(len(node.next))):
          update[i].next[i] = node.next[i]
          if self.head.next[i] is None:
            self.head.next.pop()
            self.levels -= 1
      return True
    else:
      return False

  def display(self) -> None:
    for i in range(len(self.head.next) - 1, -1, -1):
      x, s = self.head, ''
      while x.next[i] != None:
        s += str(x.next[i].val) + '(' + str(x.next[i].count) + ') -- '
        x = x.next[i]
      print('level', '{:4d}'.format(i), ':',  s)

  def search(self, target: int) -> bool:
    return self._search(target) is not None

  def add(self, num: int) -> None:
    return self._insert(num)

  def erase(self, num: int) -> bool:
    return self._delete(num)

def __starting_point():
  skiplist = Skiplist()
  skiplist.add(1)
  skiplist.add(2)
  skiplist.add(3)
  print(skiplist.search(0))
  skiplist.add(4)
  skiplist.add(2)
  print(skiplist.display())
  print(skiplist.search(1))
  skiplist.erase(0)
  skiplist.erase(1)
  print(skiplist.search(1))
  skiplist.erase(2)
  print(skiplist.search(2))
  print(skiplist.display())
__starting_point()

class Node(object):
    def __init__(self, val):
        self.val = val
        self.cnt = 1
        self.right = None
        self.down = None

import random
class Skiplist:

    def __init__(self):
        self.root = Node(float('-inf'))
        p = self.root
        for _ in range(31):
            p.down = Node(float('-inf'))
            p = p.down
        self.root.right = Node(float('inf'))
        uplevel = self.root
        clevel = self.root.down
        while clevel:
            clevel.right = Node(float('inf'))
            uplevel.right.down = clevel.right
            uplevel = clevel
            clevel = clevel.down

    def search(self, target: int) -> bool:
        p = self.root
        while p:
            if p.val == target:
                return p.cnt > 0
            elif p.right.val <= target:
                p = p.right
            else:
                p = p.down
        return False
            
    def add(self, num: int) -> None:
        p = self.root
        path = []
        while p:
            if p.val == num:
                while p:
                    p.cnt += 1
                    p = p.down
                return
            elif p.right.val <= num:
                p = p.right
            else:
                path.append(p)
                p = p.down
        node = Node(num)
        node.right = path[-1].right
        path[-1].right = node
        path.pop(-1)
        while path and random.random() < 0.5:
            last_level = path.pop(-1)
            new_node = Node(num)
            new_node.right = last_level.right
            last_level.right = new_node
            new_node.down = node
            node = new_node

    def erase(self, target: int) -> bool:
        p = self.root
        while p:
            if p.val == target:
                if p.cnt > 0:
                    while p:
                        p.cnt -= 1
                        p = p.down
                    return True
                else:
                    return False
            elif p.right.val <= target:
                p = p.right
            else:
                p = p.down
        return False


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node:
    def __init__(self, v=None):
        self.val = v
        self.right = None
        self.down = None
        

class Skiplist:

    def __init__(self, level=16):
        self.level = level
        self.levels = []
        n = None
        for i in range(level):
            node = Node(-float('inf'))
            if self.levels:
                self.levels[-1].down = node
            self.levels.append(node)
            

    def _iter(self, target):
        n = self.levels[0]
        res = []
        for i in range(self.level):
            while n and n.right and n.val < target and n.right.val < target:
                n = n.right
            res.append(n)
            n = n.down
        return res
    
    
    def search(self, target: int) -> bool:
        ns = self._iter(target)
        n = ns[-1]
        return n.right and n.right.val == target
            
            

    def add(self, num: int) -> None:
        prev = None
        for n in reversed(self._iter(num)):
            if prev and random.random() < 0.5:
                return
            node = Node(num)
            r = n.right
            n.right = node
            node.right = r
            node.down = prev
            prev = node
        

    def erase(self, num: int) -> bool:
        for i, n in enumerate(reversed(self._iter(num))):
            if i == 0:
                if not n.right or n.right.val != num:
                    return False
            if n.right:
                n.right = n.right.right
            else:
                break
        return True
            


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class LinkedList:
    
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None


class Skiplist:

    def __init__(self):
        self.levels = [LinkedList(-1) for _ in range(30)]
        for u, d in zip(self.levels[:-1], self.levels[1:]):
            u.down = d

    def search(self, target: int) -> bool:
        pointer = self.levels[0]
        while pointer:
            if pointer.__next__ != None and pointer.next.val < target:
                pointer = pointer.__next__
            elif pointer.__next__ != None and pointer.next.val == target:
                return True
            else:
                pointer = pointer.down
        return False

    def add(self, num: int) -> None:
        stack = []
        pre = None
        pointer = self.levels[0]
        
        while pointer:
            if pointer.__next__ != None and pointer.next.val <= num:
                pointer = pointer.__next__
            else:#if pointer.next != None and pointer.next.val > target:
                stack.append(pointer)
                pointer = pointer.down
        while stack:
            pointer = stack.pop(-1)
            newNode = LinkedList(num)
            newNode.next, pointer.next = pointer.next, newNode
            if pre:
                newNode.down = pre
            pre = newNode
            if random.randrange(2): break

    def erase(self, num: int) -> bool:
        found = False
        pointer = self.levels[0]
        while pointer:
            if pointer.__next__ != None and pointer.next.val < num:
                pointer = pointer.__next__
            elif pointer.__next__ != None and pointer.next.val == num:
                pointer.next = pointer.next.__next__
                found = True
                pointer = pointer.down
            else:
                pointer = pointer.down
        return found


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


import random
class Node:
    def __init__(self,val):
        self.val=val
        self.next=None
        self.down=None
    
class Skiplist:

    def __init__(self):
        self.levels=[Node(-1) for i in range(16)]
        for i in range(0,15):
            self.levels[i].down=self.levels[i+1]
        self.arr=[]
    
    def coinflip(self):
        a=random.random()>0.5
        return a
    
    def searchpath(self,value):
        self.arr=[]
        for i in range(16):
            self.arr.append(self.levels[i])
        curlevelhead=self.levels[0]
        i=0
        while(i<16):
            while(curlevelhead):
                if curlevelhead.val<value:
                    # print(\"check\",i,curlevelhead.val,curlevelhead.down)
                    self.arr[i]=curlevelhead
                    prev=curlevelhead
                    curlevelhead=curlevelhead.next
                else:
                    break
    
            i+=1
            if i!=16:
                curlevelhead=prev.down
        
    def search(self, target: int) -> bool:
        self.searchpath(target)
        if self.arr[15].next and self.arr[15].next.val==target:
            return True
        return False
        
    def add(self, num: int) -> None:
        self.searchpath(num)
        # print(arr)
        if self.arr[15].next and self.arr[15].next==num:
            a=1
        else:
            i=1
            prev=None
            check=True
            while(i<=16):
                temp=self.arr[16-i].next
                self.arr[16-i].next=Node(num)
                self.arr[16-i].next.next=temp

                if prev:
                    self.arr[16-i].next.down=prev
                prev=self.arr[16-i].next
                check=self.coinflip()
                if check ==True:
                    # print(\"coinflip\",\"add\",num,i+1)
                    i+=1
                elif check == False:
                    return        

    def erase(self, num: int) -> bool:
        
        print(\"3\",num)
        self.searchpath(num)
        i=1
        check=False
        while(i<=16):
            temp=self.arr[16-i].next
            if temp and temp.val==num:
                check=True
                self.arr[16-i].next=self.arr[16-i].next.next
            i+=1
        return check
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

import random
class Node:
    def __init__(self,val):
        self.val=val
        self.next=None
        self.down=None
    
class Skiplist:

    def __init__(self):
        self.levels=[Node(-1) for i in range(16)]
        for i in range(0,15):
            self.levels[i].down=self.levels[i+1]
        self.arr=[]
    
    def coinflip(self):
        a=random.random()>0.5
        return a
    
    def searchpath(self,value):
        self.arr=[]
        for i in range(16):
            self.arr.append(self.levels[i])
        curlevelhead=self.levels[0]
        i=0
        while(i<16):
            while(curlevelhead):
                if curlevelhead.val<value:
                    self.arr[i]=curlevelhead
                    prev=curlevelhead
                    curlevelhead=curlevelhead.__next__
                else:
                    break
    
            i+=1
            if i!=16:
                curlevelhead=prev.down
        
    def search(self, target: int) -> bool:
        self.searchpath(target)
        if self.arr[15].__next__ and self.arr[15].next.val==target:
            return True
        return False
        
    def add(self, num: int) -> None:
        self.searchpath(num)
        # print(arr)
        if self.arr[15].__next__ and self.arr[15].__next__==num:
            a=1
        else:
            i=1
            prev=None
            check=True
            while(i<=16):
                temp=self.arr[16-i].__next__
                self.arr[16-i].next=Node(num)
                self.arr[16-i].next.next=temp

                if prev:
                    self.arr[16-i].next.down=prev
                prev=self.arr[16-i].__next__
                check=self.coinflip()
                if check ==True:
                    # print(\"coinflip\",\"add\",num,i+1)
                    i+=1
                elif check == False:
                    return        

    def erase(self, num: int) -> bool:
        self.searchpath(num)
        i=1
        check=False
        while(i<=16):
            temp=self.arr[16-i].__next__
            if temp and temp.val==num:
                check=True
                self.arr[16-i].next=self.arr[16-i].next.__next__
            i+=1
        return check
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


import random
class Node:
    def __init__(self,val):
        self.val=val
        self.next=None
        self.down=None
    
class Skiplist:

    def __init__(self):
        self.levels=[Node(-1) for i in range(16)]
        for i in range(0,15):
            self.levels[i].down=self.levels[i+1]
        self.maxlevel=1
        self.arr=[]
    
    def coinflip(self):
        a=random.random()>0.5
        return a
    
    def searchpath(self,value):
        m=self.maxlevel
        self.arr=[]
        for i in range(16):
            self.arr.append(self.levels[i])
        curlevelhead=self.levels[0]
        # print(\"value\",value)
        i=0
        while(i<16):
            
            while(curlevelhead):
                if curlevelhead.val<value:
                    # print(\"check\",i,curlevelhead.val,curlevelhead.down)
                    self.arr[i]=curlevelhead
                    prev=curlevelhead
                    curlevelhead=curlevelhead.next
                else:
                    break
    
            i+=1
            if i!=16:
                curlevelhead=prev.down
        

    def search(self, target: int) -> bool:
        self.searchpath(target)
        # if self.arr[15].next:
        #     print(\"Search\",self.arr[15].next.val)
        if self.arr[15].next and self.arr[15].next.val==target:
            return True
        return False
        
    def add(self, num: int) -> None:
        print(\"2\",num)
        self.searchpath(num)
        # print(arr)
        if self.arr[15].next and self.arr[15].next==num:
            a=1
        else:
            # head=self.levels[15]
            # print(\"printing added value before\")
            # while(head):
            #     print(head.val,end=\" \")
            #     head=head.next
            # print(\"\")
            i=1
            prev=None
            check=True
            while(i<=16):
                temp=self.arr[16-i].next
                # if temp:
                #     print(temp.val,\"10\")
                #     swapobj=temp.next
                #     temp.next=Node(num)
                #     temp.next.next=swapobj
                #     if prev:
                #         temp.next.down=prev
                #     prev=temp.next
                # else:
                self.arr[16-i].next=Node(num)
                self.arr[16-i].next.next=temp

                if prev:
                    self.arr[16-i].next.down=prev
                prev=self.arr[16-i].next
                check=self.coinflip()
                if check ==True:
                    # print(\"coinflip\",\"add\",num,i+1)
                    i+=1
                elif check == False:
                    head=self.levels[15]
                    # print(\"printing added value\")
                    # while(head):
                    #     print(head.val,end=\" \")
                    #     head=head.next
                    # print(\" \")
                    return 
            
                

    def erase(self, num: int) -> bool:
        
        print(\"3\",num)
        self.searchpath(num)
        i=1
        check=False
        while(i<=16):
           
            temp=self.arr[16-i].next
            if temp and temp.val==num:
                check=True
                self.arr[16-i].next=self.arr[16-i].next.next
            i+=1
        head=self.levels[15]
        # print(\"erasing value\")
        # while(head):
        #     print(head.val,end=\" \")
        #     head=head.next
        # print(\" \")
        return check
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

class Node:
    def __init__(self,val,lev,count = 1):
        self.val = val
        self.next = [None]*lev
        self.count = count

class Skiplist:

    def __init__(self,p = 0.5):
        self.p = p
        self.head = Node(None,1)
        self.levels = 1
        
    def _random_level(self):
        _level = 1
        while random.random()<self.p:
            _level += 1
        return _level
    def _update(self,val):
        update = [None]*self.levels
        x = self.head
        for i in reversed(list(range(self.levels))):
            while x.next[i] is not None and x.next[i].val < val:
                x = x.next[i]
            update[i] = x
        return update
    def _search(self,val,update=None):
        if update is None:
            update = self._update(val)
        if len(update) > 0:
            node = update[0].next[0]
        if node is not None and node.val == val:
            return node
        return None
    
    def _insert(self,val):
        node = self._search(val)
        if node is not None:
            node.count += 1
        else:
            node = Node(val,self._random_level())
            self.levels = max(self.levels,len(node.__next__))
            while len(self.head.__next__)<len(node.__next__):
                self.head.next.append(None)
            update = self._update(val)
            for i in range(len(node.__next__)):
                node.next[i] = update[i].next[i]
                update[i].next[i] = node
        return None
    def _delete(self,val):
        update = self._update(val)
        node = self._search(val,update)
        if node is not None:
            node.count -= 1
            if node.count < 1:
                for i in reversed(list(range(len(node.__next__)))):
                    update[i].next[i] = node.next[i]
                    if self.head.next[i] is None:
                        self.head.next.pop()
                        self.levels -= 1
            return True
        else:
             return False

        

    def search(self, target: int) -> bool:
        return self._search(target) is not None

    def add(self, num: int) -> None:
        return self._insert(num)

    def erase(self, num: int) -> bool:
        return self._delete(num)


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


from random import uniform,seed
class Node:
    def __init__(self, val):
        self.nexts = []
        self.val = val
    def __getitem__(self, i):
        return self.nexts[i]
    def __setitem__(self, i, n):
        if i == len(self.nexts):
            self.nexts.append(n)
        else:
            self.nexts[i] = n
    def nval(self, i):
        return self.nexts[i].val if self.nexts[i] else 100000
class Skiplist:
    def __init__(self):
        self.prob = 0.3333
        self.start = Node(-1)
    def level(self):
        return len(self.start.nexts)
    def grow(self, node):
        d = 0
        while d==0 or uniform(0, 1) < self.prob:
            node[d] = None
            if self.level()-1 < d:
                self.start[d] = node
            d += 1
        return d
    def findall(self, target: int) -> bool:
        # Invariance: cur.val < target <= rval
        cur = self.start
        for i in range(self.level()-1, -1, -1):
            while not cur.val<=target<=cur.nval(i):
                cur = cur[i]
            yield i, cur
    def search(self, target: int) -> bool:
        return any(p.nval(i)==target for i,p in self.findall(target))
    def add(self, num: int) -> None:
        preds = list(self.findall(num))
        cur = Node(num)
        d = self.grow(cur)
        for i, prev in reversed(preds[-d:]):
            cur[i] = prev[i]
            prev[i] = cur
    def erase(self, num: int) -> bool:
        preds = [p for i,p in self.findall(num)][::-1]
        if not preds or preds[0].nval(0) != num:
            return False
        rem = preds[0][0]
        for i, p in enumerate(preds):
            if p[i] is rem:
                p[i] = p[i][i]
        while self.start and self.start[self.level()-1] is None:
            self.start.nexts.pop()
        return True
            
    def debug(self):
        print(\"Depth = \", self.level())
        for i in range(self.level()):
            cur = self.start[i]
            level = []
            while cur:
                level.append(cur.val)
                cur = cur[i]
            print(\"Level\", i, level)

from random import uniform,seed
class Node:
    def __init__(self, val):
        self.nexts = []
        self.val = val
    def __getitem__(self, i):
        return self.nexts[i]
    def __setitem__(self, i, n):
        if i == len(self.nexts):
            self.nexts.append(n)
        else:
            self.nexts[i] = n
    def nval(self, i):
        return self.nexts[i].val if self.nexts[i] else 100000
class Skiplist:
    def __init__(self):
        self.prob = 0.25
        self.start = Node(-1)
    def level(self):
        return len(self.start.nexts)
    def grow(self, node):
        d = 0
        while d==0 or uniform(0, 1) < self.prob:
            node[d] = None
            if self.level()-1 < d:
                self.start[d] = node
            d += 1
        return d
    def findall(self, target: int) -> bool:
        # Invariance: cur.val < target <= rval
        cur = self.start
        for i in range(self.level()-1, -1, -1):
            while not cur.val<=target<=cur.nval(i):
                cur = cur[i]
            yield i, cur
    def search(self, target: int) -> bool:
        return any(p.nval(i)==target for i,p in self.findall(target))
    def add(self, num: int) -> None:
        preds = list(self.findall(num))
        cur = Node(num)
        d = self.grow(cur)
        for i, prev in reversed(preds[-d:]):
            cur[i] = prev[i]
            prev[i] = cur
    def erase(self, num: int) -> bool:
        preds = [p for i,p in self.findall(num)][::-1]
        if not preds or preds[0].nval(0) != num:
            return False
        rem = preds[0][0]
        for i, p in enumerate(preds):
            if p[i] is rem:
                p[i] = p[i][i]
        while self.start and self.start[self.level()-1] is None:
            self.start.nexts.pop()
        return True
            
    def debug(self):
        print(\"Depth = \", self.level())
        for i in range(self.level()):
            cur = self.start[i]
            level = []
            while cur:
                level.append(cur.val)
                cur = cur[i]
            print(\"Level\", i, level)



class Skiplist:

  def __init__(self):
    self.data_set = defaultdict(int)
    pass
  def search(self, target: int) -> bool:
    if target in self.data_set:
      return True
    return False

  def add(self, num: int) -> None:
    self.data_set[num] += 1
    return

  def erase(self, num: int) -> bool:
    if num in self.data_set:
      self.data_set[num] -= 1
      if self.data_set[num] == 0:
        del self.data_set[num]
      return True
    return False

class Node:
    def __init__(self,v,i):
        self.v = (v,i)
        self.next = None
class Skiplist:
    def __init__(self):
        self.Levels = []
        self.Levels.append(Node(-1,-1))
        self.Levels[0].next = Node(10000000,10000000)
        self.Hash = {(-1,-1):[self.Levels[0]]}
    def search(self, target: int) -> bool:
        # print('search',target)
        # for l in self.Levels:
        #     print('new level')
        #     while l:
        #         print(l.v)
        #         l = l.next
        height = len(self.Levels)-1
        start = self.Levels[-1]
        old = self.Levels[-1]
        while height >= 0:
            start = self.Hash[old.v][height]
            while start.v[0] <= target:
                old = start
                new = start.__next__
                start = start.__next__
            if old.v[0] == target:
                return True
            height -= 1
        return False
    def add(self, num: int) -> None:
        # print('add',num)
        cand = []
        height = len(self.Levels)-1
        # start = self.Levels[-1]
        # start = self.Hash[old.v][height]
        old = self.Levels[-1]
        while height >= 0:
            start = self.Hash[old.v][height]
            while start.v[0] <= num:
                old = start
                new = start.__next__
                start = start.__next__
            cand.append(old)
            height -= 1
        # print(cand)
        i,flag = len(cand)-1,True
        new = (num,cand[-1].v[1]+1) if cand[-1].v[0] == num else (num,0)
        self.Hash[new] = []
        while flag:
            node = Node(new[0],new[1])
            self.Hash[new].append(node)
            if i>=0:
                left,right = cand[i],cand[i].__next__
                left.next = node
                node.next = right
                i -= 1
            else:
                t = Node(-1,-1)
                self.Hash[(-1,-1)].append(t)
                self.Levels.append(t)
                self.Levels[-1].next = node
                node.next = Node(10000000,10000000)
            flag = random.choices([True,False], [0.5,0.5])[0]
        # for l in self.Levels:
        #     print('new level')
        #     while l:
        #         print(l.v)
        #         l = l.next
    def erase(self, num: int) -> bool:
        # print('erase',num)
        cand = []
        height = len(self.Levels)-1
        old = self.Levels[-1]
        while height >= 0:
            start = self.Hash[old.v][height]
            while start.v[0] < num:
                old = start
                new = start.__next__
                start = start.__next__
            cand.append(old)
            height -= 1
        todel = cand[-1].__next__
        if todel.v[0] != num:
            return False
        l = len(cand)
        # for c in cand:
        #     print(c.v)
        for i in range(l-1,-1,-1):
            if cand[i].next.v == todel.v:
                t = cand[i].__next__
                cand[i].next = t.__next__
                t.next = None
            else:
                break
        del self.Hash[todel.v]
        # for l in self.Levels:
        #     print('new level')
        #     while l:
        #         print(l.v)
        #         l = l.next
        return True


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


from random import uniform,seed
class Node:
    def __init__(self, val):
        self.nexts = []
        self.val = val
    def __getitem__(self, i):
        return self.nexts[i]
    def __setitem__(self, i, n):
        if i == len(self.nexts):
            self.nexts.append(n)
        else:
            self.nexts[i] = n
    def nval(self, i):
        return self.nexts[i].val if self.nexts[i] else 100000
class Skiplist:
    def __init__(self):
        self.prob = 0.5
        self.start = Node(-1)
    def level(self):
        return len(self.start.nexts)
    def grow(self, node):
        d = 0
        while d==0 or uniform(0, 1) < self.prob:
            node[d] = None
            if self.level()-1 < d:
                self.start[d] = node
            d += 1
        return d
    def findall(self, target: int) -> bool:
        # Invariance: cur.val < target <= rval
        cur = self.start
        for i in range(self.level()-1, -1, -1):
            while not cur.val<=target<=cur.nval(i):
                cur = cur[i]
            yield i, cur
    def search(self, target: int) -> bool:
        return any(p.nval(i)==target for i,p in self.findall(target))
    def add(self, num: int) -> None:
        preds = list(self.findall(num))
        cur = Node(num)
        d = self.grow(cur)
        for i, prev in reversed(preds[-d:]):
            cur[i] = prev[i]
            prev[i] = cur
    def erase(self, num: int) -> bool:
        preds = [p for i,p in self.findall(num)][::-1]
        if not preds or preds[0].nval(0) != num:
            return False
        rem = preds[0][0]
        for i, p in enumerate(preds):
            if p[i] is rem:
                p[i] = p[i][i]
        while self.start and self.start[self.level()-1] is None:
            self.start.nexts.pop()
        return True
            
    def debug(self):
        print(\"Depth = \", self.level())
        for i in range(self.level()):
            cur = self.start[i]
            level = []
            while cur:
                level.append(cur.val)
                cur = cur[i]
            print(\"Level\", i, level)

from random import uniform,seed
class Node:
    def __init__(self, val):
        self.nexts = []
        self.val = val
    def __getitem__(self, i):
        return self.nexts[i]
    def __setitem__(self, i, n):
        if i == len(self.nexts):
            self.nexts.append(n)
        else:
            self.nexts[i] = n
    def nval(self, i):
        return self.nexts[i].val if self.nexts[i] else 100000
class Skiplist:
    def __init__(self):
        self.prob = 0.5
        self.start = Node(-1)
    def level(self):
        return len(self.start.nexts)
    def grow(self, node):
        d = 0
        while d==0 or uniform(0, 1) < self.prob:
            node[d] = None
            if self.level()-1 < d:
                self.start[d] = node
            d += 1
        return d
    def findall(self, target: int) -> bool:
        # Invariance: cur.val < target <= rval
        cur = self.start
        for i in range(self.level()-1, -1, -1):
            while not cur.val<=target<=cur.nval(i):
                cur = cur[i]
            yield i, cur
    def search(self, target: int) -> bool:
        return any(p.nval(i)==target for i,p in self.findall(target))
    def add(self, num: int) -> None:
        preds = list(self.findall(num))
        cur = Node(num)
        d = self.grow(cur)
        for i, prev in reversed(preds[-d:]):
            cur[i] = prev[i]
            prev[i] = cur
    def erase(self, num: int) -> bool:
        preds = []
        erased = False
        for i,p in self.findall(num):
            if p.nval(i)==num:
                p[i] = p[i][i]
                erased = True
                if p==self.start and p[i] is None:
                    self.start.nexts.pop()
        return erased
    def debug(self):
        print(\"Depth = \", self.level())
        for i in range(self.level()):
            cur = self.start[i]
            level = []
            while cur:
                level.append(cur.val)
                cur = cur[i]
            print(\"Level\", i, level)

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

class Node(object): 
    def __init__(self,val): self.val,self.next, self.down = val, None, None
        
class Skiplist(object):
    def __init__(self, levels = 30):
        self.heads = [Node(-float('inf')) for _ in range(levels)]
        for c,n in zip(self.heads, self.heads[1:]): c.down = n
                    
    def search(self, target):
        cur = self.heads[0]
        while(cur):
            if cur.__next__ is None or cur.val < target <= cur.next.val:
                if cur.__next__ and target == cur.next.val: return True
                cur = cur.down
            else: cur = cur.__next__
        return False

    def add(self, num):
        stack,cur,prev = collections.deque([]),self.heads[0], None
        while(cur):
            if cur.__next__ is None or cur.val < num  <= cur.next.val:
                stack.append(cur)
                cur = cur.down
            else: cur = cur.__next__
        while(stack):
            cur = stack.pop()
            node = Node(num)
            node.next,cur.next = cur.next, node
            if prev: node.down = prev
            prev = node
            if random.randint(0,len(self.heads)-1) < len(self.heads) -1 : break
 
    def erase(self, num):
        b,cur = False,self.heads[0]
        while(cur):
            if cur.__next__ is None or cur.val < num <= cur.next.val:
                if cur.__next__ and cur.next.val == num:  b,cur.next = True,cur.next.__next__
                cur = cur.down
            else: cur = cur.__next__   
        return b
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node(object): 
    def __init__(self,val): self.val,self.next, self.down = val, None, None
        
class Skiplist(object):
    def __init__(self, levels = 30):
        self.heads = [Node(-float('inf')) for _ in range(levels)]
        for c,n in zip(self.heads, self.heads[1:]): c.down = n
                    
    def search(self, target):
        cur = self.heads[0]
        while(cur):
            if cur.next is None or cur.val < target <= cur.next.val:
                if cur.next and target == cur.next.val: return True
                cur = cur.down
            else: cur = cur.next
        return False

    def add(self, num):
        stack,cur,prev = collections.deque([]),self.heads[0], None
        while(cur):
            if cur.next is None or cur.val < num  <= cur.next.val:
                stack.append(cur)
                cur = cur.down
            else: cur = cur.next
        while(stack):
            cur = stack.pop()
            node = Node(num)
            node.next,cur.next = cur.next, node
            if prev: node.down = prev
            prev = node
            if random.randint(0,len(self.heads)-1) < len(self.heads) -1 : break
 
    def erase(self, num):
        b,cur = False,self.heads[0]
        while(cur):
            if cur.next is None or cur.val < num <= cur.next.val:
                if cur.next and cur.next.val == num:  b,cur.next = True,cur.next.next
                cur = cur.down
            else: cur = cur.next   
        return b

class Node(object): 
    def __init__(self,val): self.val,self.next, self.down = val, None, None
        
class Skiplist(object):
    def __init__(self, levels = 30):
        self.heads = [Node(-float('inf')) for _ in range(levels)]
        for c,n in zip(self.heads, self.heads[1:]): c.down = n
                    
    def search(self, target):
        cur = self.heads[0]
        while(cur):
            if cur.__next__ is None or cur.val < target <= cur.next.val:
                if cur.__next__ and target == cur.next.val: return True
                cur = cur.down
            else: cur = cur.__next__
        return False

    def add(self, num):
        stack,cur,prev = collections.deque([]),self.heads[0], None
        while(cur):
            if cur.__next__ is None or cur.val < num  <= cur.next.val:
                stack.append(cur)
                cur = cur.down
            else: cur = cur.__next__
        while(stack):
            cur = stack.pop()
            node = Node(num)
            node.next,cur.next = cur.next, node
            if prev: node.down = prev
            prev = node
            if random.randint(0,len(self.heads)-1) < len(self.heads) -1 : break
 
    def erase(self, num):
        b,cur = False,self.heads[0]
        while(cur):
            if cur.__next__ is None or cur.val < num <= cur.next.val:
                if cur.__next__ and cur.next.val == num:  b,cur.next = True,cur.next.__next__
                cur = cur.down
            else: cur = cur.__next__   
        return b

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node(object): 
    def __init__(self,val): 
        self.val,self.next, self.down = val, None, None
        
class Skiplist(object):
    def __init__(self, levels = 30):
        self.heads = [Node(-float('inf')) for _ in range(levels)]
        for c,n in zip(self.heads, self.heads[1:]): c.down = n
                    
    def search(self, target):
        cur = self.heads[0]
        while(cur):
            if cur.next is None or cur.val < target <= cur.next.val:
                if cur.next and target == cur.next.val: 
                    return True
                cur = cur.down
            else: 
                cur = cur.next
        return False

    def add(self, num):
        stack,cur,prev = collections.deque([]),self.heads[0], None
        while(cur):
            if cur.next is None or cur.val < num  <= cur.next.val:
                stack.append(cur)
                cur = cur.down
            else: cur = cur.next
        while(stack):
            cur = stack.pop()
            node = Node(num)
            node.next,cur.next = cur.next, node
            if prev: node.down = prev
            prev = node
            if random.randint(0,len(self.heads)-1) < len(self.heads) -1 : break
 
    def erase(self, num):
        b,cur = False,self.heads[0]
        while(cur):
            if cur.next is None or cur.val < num <= cur.next.val:
                if cur.next and cur.next.val == num:  b,cur.next = True,cur.next.next
                cur = cur.down
            else: cur = cur.next   
        return b

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None


from collections import deque
import random
class Skiplist:
    def __init__(self, levels = 30):
        self.heads = [Node(-float('inf')) for _ in range(levels)]
        for c,n in zip(self.heads, self.heads[1:]): # the lenght of zipped elements can be different
            c.down = n

    def search(self, target) -> bool:
        curr = self.heads[0] #-inf
        while curr:
            if curr.next is None or curr.val < target <= curr.next.val:
                if curr.next and target == curr.next.val:
                    return True
                curr = curr.down
            else:
                curr = curr.next
        return False

    def add(self, num: int) -> None:
        stack, curr, pre = deque([]), self.heads[0], None
        while curr:
            if curr.next is None or curr.val < num <= curr.next.val:
                stack.append(curr)
                curr = curr.down
            else:
                curr = curr.next

        while stack:
            curr = stack.pop()
            node = Node(num)
            node.next, curr.next = curr.next, node
            if pre:
                node.down = pre
            pre = node
            if random.randint(0, len(self.heads)-1) <  len(self.heads)-1:
                break

    def erase(self, num: int) -> bool:
        b, curr = False, self.heads[0]
        while curr:
            if curr.next is None or curr.val < num <= curr.next.val:
                if curr.next and curr.next.val == num:
                    b, curr.next = True, curr.next.next
                curr = curr.down
            else:
                curr = curr.next
        return b

class ListNode:
    
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None


class Skiplist:

    def __init__(self):
        self.levels = []
        
        # Because the number of calls is <50000, and 2^16>60000, which is enough to handle all calls.
        # Otherwise we need to consider the situation new level need to be added when level not being enough.
        vertical = None
        for _ in range(16):
            head = ListNode(float(\"-inf\"))  # 新建一些dummyhead放到每一层的头部
            self.levels.append(head)        # 处理each level - horizontal
            if vertical:                        # 处理verticals
                vertical.down = head
            vertical = head
            
    def _find_smaller(self, target):
        \"\"\"
        helper function to find the largest node that is smaller than search target in EACH levels
        and store them in a list, return the list
        \"\"\"
        res = []
        
        curr = self.levels[0]
        while curr:
            while curr.next and curr.next.val < target:
                curr = curr.next
            res.append(curr)    # on each level, just append the largest node that is smaller than target
            
            curr = curr.down
            
        return res

    def search(self, target: int) -> bool:
        last = self._find_smaller(target)[-1]   # last is just smaller node on the last level
        if last.next and last.next.val == target:
            return True
        return False

    def add(self, num: int) -> None:
        smaller = self._find_smaller(num) # the idea is to insert a new_node at the right place, we find the right place at each level first
        vertical = None
        for node in smaller[::-1]:      # If we add a node in a level, all levels after that also need to be added, so loop reversely
            new_node = ListNode(num)    # the idea is to insert a new_node at the right place, we create a new node first
            
            # firstly, insert the new_node to the level - horizontal
            new_node.next = node.next
            node.next = new_node
            
            # then, point the new_node.down to it's corresponding down node - vertical
            new_node.down = vertical
            vertical = node
            
            # we don't insert the new_node to every level, we only inser the new_node to some levesl on the bottom
            # how to we decide which levels to insert? we use coin toss
            # The purpose of coin toss is to ensure that each node at current level will be 
            # duplicated to its upper level with a probability of 0.5, 
            # so the number of nodes at the upper level is roughly half of the current level.
            # So in the extreme case, SkipList is equivalent to a balanced binary search tree.
            # that is why add, erase and search can be O(logn)
            rand = random.randrange(0, 10)
            if rand >= 5:   # half of the possibility that we stop inserting the new_node to any upper levels
                break

    def erase(self, num: int) -> bool:
        smaller = self._find_smaller(num)
        found = False
        for node in smaller[::-1]:
            if node.next and node.next.val == num:
                node.next = node.next.next  # remove the node
                found = True
        return found


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

class Skiplist:

    def __init__(self):
        self.nums = []

    def search(self, target: int) -> bool:
        if not self.nums:
            return False
        idx = bisect.bisect_left(self.nums, target)
        if idx < len(self.nums) and self.nums[idx] == target:
            return True
        return False
        

    def add(self, num: int) -> None:
        bisect.insort(self.nums, num)
        

    def erase(self, num: int) -> bool:
        if not self.search(num):
            return False
        idx = bisect.bisect_left(self.nums, num)
        self.nums.pop(idx)
        return True
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Skiplist:
    class Node:
        __slots__ = 'value', 'next'
        def __init__(self, value):
            self.value = value
            self.next = []

    def __init__(self):
        self.max_height = 1
        self.left = self.Node(-float('inf'))
        self.right = self.Node(float('inf'))
        self.left.next.append(self.right)

    def _find(self, target: int) -> bool:
        path = []
        h = len(self.left.__next__) - 1
        pointer = self.left
        while h > -1:
            while pointer.next[h].value < target:
                pointer = pointer.next[h]
            path.append(copy.copy(pointer))
            h -= 1
        return path
        
    def search(self, target: int) -> bool:
        h = len(self.left.__next__) - 1
        pointer = self.left
        while h > -1:
            while pointer.next[h].value <= target:
                pointer = pointer.next[h]
                if pointer.value == target:
                    return True
            h -= 1
        return False
    
    def add(self, num: int) -> None:
        height = 0
        while random.randint(0,1):
            height += 1
        while height >= len(self.left.__next__):
            self.left.next.append(self.right)
        path = self._find(num)
        new = self.Node(num)
        for h in range(height+1):
            prev = path[-1-h]
            new.next.append(prev.next[h])
            prev.next[h] = new
            
    def erase(self, num: int) -> bool:
        path = self._find(num)
        node = path[-1].next[0]
        if node.value != num:
            return False
        for i, x in enumerate(node.__next__):
            path[-1-i].next[i] = x
        return True
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class LinkedList:
    
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None


class Skiplist:

    def __init__(self):
        self.levels = [LinkedList(-1) for _ in range(100)]
        for u, d in zip(self.levels[:-1], self.levels[1:]):
            u.down = d

    def search(self, target: int) -> bool:
        pointer = self.levels[0]
        while pointer:
            if pointer.__next__ != None and pointer.next.val < target:
                pointer = pointer.__next__
            elif pointer.__next__ != None and pointer.next.val == target:
                return True
            else:
                pointer = pointer.down
        return False

    def add(self, num: int) -> None:
        stack = []
        pre = None
        pointer = self.levels[0]
        
        while pointer:
            if pointer.__next__ != None and pointer.next.val <= num:
                pointer = pointer.__next__
            else:#if pointer.next != None and pointer.next.val > target:
                stack.append(pointer)
                pointer = pointer.down
        while stack:
            pointer = stack.pop(-1)
            newNode = LinkedList(num)
            newNode.next, pointer.next = pointer.next, newNode
            if pre:
                newNode.down = pre
            pre = newNode
            if random.randrange(2): break

    def erase(self, num: int) -> bool:
        found = False
        pointer = self.levels[0]
        while pointer:
            if pointer.__next__ != None and pointer.next.val < num:
                pointer = pointer.__next__
            elif pointer.__next__ != None and pointer.next.val == num:
                pointer.next = pointer.next.__next__
                found = True
                pointer = pointer.down
            else:
                pointer = pointer.down
        return found


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Skiplist:
    class Node:
        __slots__ = 'value', 'next'
        def __init__(self, value):
            self.value = value
            self.next = []

    def __init__(self):
        self.max_height = 1
        self.left = self.Node(-float('inf'))
        self.right = self.Node(float('inf'))
        self.left.next.append(self.right)

    def _find(self, target: int) -> bool:
        path = []
        h = len(self.left.__next__) - 1
        pointer = self.left
        while h > -1:
            while pointer.next[h].value < target:
                pointer = pointer.next[h]
            path.append(copy.copy(pointer))
            h -= 1
        return path
        
    def search(self, target: int) -> bool:
        h = len(self.left.__next__) - 1
        pointer = self.left
        while h > -1:
            while pointer.next[h].value <= target:
                pointer = pointer.next[h]
                if pointer.value == target:
                    return True
            h -= 1
        return False
    
    def add(self, num: int) -> None:
        path = self._find(num)
        height = 0
        while random.randint(0,1):
            height += 1
        while height >= len(self.left.__next__):
            self.left.next.append(self.right)
        new = self.Node(num)
        for h in range(height+1):
            try:
                prev = path[-1-h]
            except IndexError:
                prev = self.left
            new.next.append(prev.next[h])
            prev.next[h] = new
            
    def erase(self, num: int) -> bool:
        path = self._find(num)
        node = path[-1].next[0]
        if node.value != num:
            return False
        for i, x in enumerate(node.__next__):
            path[-1-i].next[i] = x
        return True
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node:
    __slots__ = 'val', 'levels'
    def __init__(self, val, levels):
        self.val = val
        self.levels = [None] * levels

class Skiplist(object):
    def __init__(self):
        self.head = Node(-1, 16) 
    
    def _iter(self, num):
        cur = self.head
        for level in range(15, -1, -1):
            while True:
                nxt = cur.levels[level]
                if nxt and nxt.val < num:
                    cur = nxt
                else:
                    break
            yield cur, level

    def search(self, target):
        for prev, level in self._iter(target): pass
        cur = prev.levels[0]
        return cur and cur.val == target

    def add(self, num):
        nodelvls = random.randint(1,16)
        node = Node(num, nodelvls)
        for cur, level in self._iter(num):
            if level >= nodelvls: continue
            future = cur.levels[level]
            cur.levels[level] = node
            node.levels[level] = future

    def erase(self, num):
        ans = False
        for cur, level in self._iter(num):
            nxt = cur.levels[level]
            if nxt and nxt.val == num:
                ans = True
                cur.levels[level] = nxt.levels[level]
        return ans

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node:
    __slots__ = 'val', 'levels'
    def __init__(self, val, levels):
        self.val = val
        self.levels = [None] * levels

class Skiplist(object):
    def __init__(self):
        self.head = Node(-1, 16) 
    
    def _iter(self, num):
        cur = self.head
        for level in range(15, -1, -1):
            while True:
                nxt = cur.levels[level]
                if nxt and nxt.val < num:
                    cur = nxt
                else:
                    break
            yield cur, level

    def search(self, target):
        for prev, level in self._iter(target):
            pass
        cur = prev.levels[0]
        return cur and cur.val == target

    def add(self, num):
        nodelvls = min(16, 1 + int(math.log2(1.0 / random.random())))
        nodelvls = random.randint(1,16)
        node = Node(num, nodelvls)
        
        for cur, level in self._iter(num):
            if level < nodelvls:
                future = cur.levels[level]
                cur.levels[level] = node
                node.levels[level] = future

    def erase(self, num):
        ans = False
        for cur, level in self._iter(num):
            nxt = cur.levels[level]
            if nxt and nxt.val == num:
                ans = True
                cur.levels[level] = nxt.levels[level]
        return ans

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Node:
    __slots__ = 'val', 'levels'
    def __init__(self, val, levels):
        self.val = val
        self.levels = [None] * levels

class Skiplist(object):
    def __init__(self):
        self.head = Node(-1, 16) 
    
    def _iter(self, num):
        cur = self.head
        for level in range(15, -1, -1):
            while True:
                nxt = cur.levels[level]
                if nxt and nxt.val < num:
                    cur = nxt
                else:
                    break
            yield cur, level

    def search(self, target):
        for prev, level in self._iter(target):
            pass
        cur = prev.levels[0]
        return cur and cur.val == target

    def add(self, num):
        nodelvls = random.randint(1,16)
        node = Node(num, nodelvls)
        for cur, level in self._iter(num):
            if level >= nodelvls: continue
            future = cur.levels[level]
            cur.levels[level] = node
            node.levels[level] = future

    def erase(self, num):
        ans = False
        for cur, level in self._iter(num):
            nxt = cur.levels[level]
            if nxt and nxt.val == num:
                ans = True
                cur.levels[level] = nxt.levels[level]
        return ans

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class LinkedList:
    
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None


class Skiplist:

    def __init__(self):
        self.levels = [LinkedList(-1) for _ in range(5)]
        for u, d in zip(self.levels[:-1], self.levels[1:]):
            u.down = d

    def search(self, target: int) -> bool:
        pointer = self.levels[0]
        while pointer:
            if pointer.__next__ != None and pointer.next.val < target:
                pointer = pointer.__next__
            elif pointer.__next__ != None and pointer.next.val == target:
                return True
            else:
                pointer = pointer.down
        return False

    def add(self, num: int) -> None:
        stack = []
        pre = None
        pointer = self.levels[0]
        
        while pointer:
            if pointer.__next__ != None and pointer.next.val <= num:
                pointer = pointer.__next__
            else:#if pointer.next != None and pointer.next.val > target:
                stack.append(pointer)
                pointer = pointer.down
        while stack:
            pointer = stack.pop(-1)
            newNode = LinkedList(num)
            newNode.next, pointer.next = pointer.next, newNode
            if pre:
                newNode.down = pre
            pre = newNode
            if random.randrange(2): break

    def erase(self, num: int) -> bool:
        found = False
        pointer = self.levels[0]
        while pointer:
            if pointer.__next__ != None and pointer.next.val < num:
                pointer = pointer.__next__
            elif pointer.__next__ != None and pointer.next.val == num:
                pointer.next = pointer.next.__next__
                found = True
                pointer = pointer.down
            else:
                pointer = pointer.down
        return found


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class ListNode:
    
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None


class Skiplist:

    def __init__(self):
        self.levels = []
        
        # Because the number of calls is <50000, and 2^16>60000, which is enough to handle all calls.
        # Otherwise we need to consider the situation new level need to be added when level not being enough.
        vertical = None
        for _ in range(16):
            head = ListNode(float(\"-inf\"))  # 新建一些dummyhead放到每一层的头部
            self.levels.append(head)        # 处理each level - horizontal
            if vertical:                        # 处理verticals
                vertical.down = head
            vertical = head
            
    def _find_smaller(self, target):
        \"\"\"
        helper function to find the largest node that is smaller than search target in EACH levels
        and store them in a list, return the list
        \"\"\"
        res = []
        
        curr = self.levels[0]
        while curr:
            while curr.next and curr.next.val < target:
                curr = curr.next
            res.append(curr)    # on each level, just append the largest node that is smaller than target
            
            curr = curr.down
            
        return res

    def search(self, target: int) -> bool:
        last = self._find_smaller(target)[-1]   # last is just smaller node on the last level
        if last.next and last.next.val == target:
            return True
        return False

    def add(self, num: int) -> None:
        smaller = self._find_smaller(num) # the idea is to insert a new_node at the right place, we find the right place at each level first
        vertical = None
        for i in range(len(smaller)-1, -1, -1):      # If we add a node in a level, all levels after that also need to be added, so loop reversely
            node = smaller[i]
            print(node.val)
            new_node = ListNode(num)    # the idea is to insert a new_node at the right place, we create a new node first
            
            # firstly, insert the new_node to the level - horizontal
            new_node.next = node.next
            node.next = new_node
            
            # then, point the new_node.down to it's corresponding down node - vertical
            new_node.down = vertical
            vertical = node
            
            # we don't insert the new_node to every level, we only inser the new_node to some levesl on the bottom
            # how to we decide which levels to insert? we use coin toss
            # The purpose of coin toss is to ensure that each node at current level will be 
            # duplicated to its upper level with a probability of 0.5, 
            # so the number of nodes at the upper level is roughly half of the current level.
            # So in the extreme case, SkipList is equivalent to a balanced binary search tree.
            # that is why add, erase and search can be O(logn)
            rand = random.randrange(0, 10)
            if rand >= 5:   # half of the possibility that we stop inserting the new_node to any upper levels
                break

    def erase(self, num: int) -> bool:
        smaller = self._find_smaller(num)
        found = False
        for node in smaller[::-1]:
            while node.next:
                if node.next.val == num:
                    node.next = node.next.next  # remove the node
                    found = True
                    break
                node = node.next
            if not node.next:   # 如果这一层都找不到num, 那上面的level更找不到了
                break
        return found


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

class Skiplist:
    class Node:
        __slots__ = 'value', 'next'
        def __init__(self, value):
            self.value = value
            self.next = []

    def __init__(self):
        self.max_height = 1
        self.left = self.Node(-float('inf'))
        self.right = self.Node(float('inf'))
        self.left.next.append(self.right)

    def _find(self, target: int) -> bool:
        path = []
        h = len(self.left.__next__) - 1
        pointer = self.left
        while h > -1:
            while pointer.next[h].value < target:
                pointer = pointer.next[h]
            path.append(copy.copy(pointer))
            h -= 1
        return path
        
    def search(self, target: int) -> bool:
        path = self._find(target)
        return path[-1].next[0].value == target
    
    def add(self, num: int) -> None:
        path = self._find(num)
        height = 0
        while random.randint(0,1):
            height += 1
        while height >= len(self.left.__next__):
            self.left.next.append(self.right)
        new = self.Node(num)
        for h in range(height+1):
            try:
                prev = path[-1-h]
            except IndexError:
                prev = self.left
            new.next.append(prev.next[h])
            prev.next[h] = new
            
    def erase(self, num: int) -> bool:
        path = self._find(num)
        node = path[-1].next[0]
        if node.value != num:
            return False
        for i, x in enumerate(node.__next__):
            path[-1-i].next[i] = x
        return True
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Skiplist:

    def __init__(self):
        self._skiplist = []

    def search(self, target: int) -> bool:
        return target in self._skiplist

    def add(self, num: int) -> None:
        start = 0
        end = len(self._skiplist)
        while start < end:
            mid = int((start + end) / 2)
            if self._skiplist[mid] < num:
                start = mid + 1
            else:
                end = mid
        self._skiplist.insert(start, num)

    def erase(self, num: int) -> bool:
        if self.search(num):
            self._skiplist.remove(num)
            return True
        else:
            return False


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Skiplist:

    def __init__(self):
        self.data = []        

    def search(self, target: int) -> bool:
        return self.data and target <= self.data[-1] and target == self.data[bisect.bisect_left(self.data, target)]

    def add(self, num: int) -> None:
        bisect.insort(self.data, num)

    def erase(self, num: int) -> bool:
        if not self.data or num > self.data[-1]:
            return False
        i = bisect.bisect_left(self.data, num)
        if self.data[i] != num:
            return False
        self.data = self.data[:i]+self.data[i+1:]
        return True        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class Skiplist:
    class Node:
        def __init__(self, value):
            self.value = value
            self.next = []

    def __init__(self):
        self.max_height = 1
        self.left = self.Node(-float('inf'))
        self.right = self.Node(float('inf'))
        self.left.next.append(self.right)

    def _find(self, target: int) -> bool:
        path = []
        h = len(self.left.__next__) - 1
        pointer = self.left
        while h > -1:
            while pointer.next[h].value < target:
                pointer = pointer.next[h]
            path.append(copy.copy(pointer))
            h -= 1
        return path
        
    def search(self, target: int) -> bool:
        path = self._find(target)
        return path[-1].next[0].value == target
    
    def add(self, num: int) -> None:
        path = self._find(num)
        height = 0
        while random.randint(0,1):
            height += 1
        while height >= len(self.left.__next__):
            self.left.next.append(self.right)
        new = self.Node(num)
        for h in range(height+1):
            try:
                prev = path[-1-h]
            except IndexError:
                prev = self.left
            new.next.append(prev.next[h])
            prev.next[h] = new
            
    def erase(self, num: int) -> bool:
        path = self._find(num)
        node = path[-1].next[0]
        if node.value != num:
            return False
        for i, x in enumerate(node.__next__):
            path[-1-i].next[i] = x
        return True
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


class ListNode:
    
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None


class Skiplist:

    def __init__(self):
        self.levels = []
        
        # Because the number of calls is <50000, and 2^16>60000, which is enough to handle all calls.
        # Otherwise we need to consider the situation new level need to be added when level not being enough.
        vertical = None
        for _ in range(16):
            head = ListNode(float(\"-inf\"))  # 新建一些dummyhead放到每一层的头部
            self.levels.append(head)        # 处理each level - horizontal
            if vertical:                        # 处理verticals
                vertical.down = head
            vertical = head
            
    def _find_smaller(self, target):
        \"\"\"
        helper function to find the largest node that is smaller than search target in EACH levels
        and store them in a list, return the list
        \"\"\"
        res = []
        
        curr = self.levels[0]
        while curr:
            while curr.next and curr.next.val < target:
                curr = curr.next
            res.append(curr)    # on each level, just append the largest node that is smaller than target
            
            curr = curr.down
            
        return res

    def search(self, target: int) -> bool:
        last = self._find_smaller(target)[-1]   # last is just smaller node on the last level
        if last.next and last.next.val == target:
            return True
        return False

    def add(self, num: int) -> None:
        smaller = self._find_smaller(num) # the idea is to insert a new_node at the right place, we find the right place at each level first
        vertical = None
        for node in smaller[::-1]:      # If we add a node in a level, all levels after that also need to be added, so loop reversely
            new_node = ListNode(num)    # the idea is to insert a new_node at the right place, we create a new node first
            
            # firstly, insert the new_node to the level - horizontal
            new_node.next = node.next
            node.next = new_node
            
            # then, point the new_node.down to it's corresponding down node - vertical
            new_node.down = vertical
            vertical = node
            
            # we don't insert the new_node to every level, we only inser the new_node to some levesl on the bottom
            # how to we decide which levels to insert? we use coin toss
            # The purpose of coin toss is to ensure that each node at current level will be 
            # duplicated to its upper level with a probability of 0.5, 
            # so the number of nodes at the upper level is roughly half of the current level.
            # So in the extreme case, SkipList is equivalent to a balanced binary search tree.
            # that is why add, erase and search can be O(logn)
            rand = random.randrange(0, 10)
            if rand >= 5:   # half of the possibility that we stop inserting the new_node to any upper levels
                break

    def erase(self, num: int) -> bool:
        smaller = self._find_smaller(num)
        found = False
        for node in smaller[::-1]:
            while node.next:
                if node.next.val == num:
                    node.next = node.next.next  # remove the node
                    found = True
                    break
                node = node.next
            if not node.next:   # 如果这一层都找不到num, 那上面的level更找不到了
                break
        return found


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

class Node(object):
    def __init__(self, val):
        self.val = val
        self.cnt = 1
        self.right = None
        self.down = None

import random
class Skiplist:

    def __init__(self):
        self.root = Node(float('-inf'))
        p = self.root
        for _ in range(3):
            p.down = Node(float('-inf'))
            p = p.down
        self.root.right = Node(float('inf'))
        uplevel = self.root
        clevel = self.root.down
        while clevel:
            clevel.right = Node(float('inf'))
            uplevel.right.down = clevel.right
            uplevel = clevel
            clevel = clevel.down

    def search(self, target: int) -> bool:
        p = self.root
        while p:
            if p.val == target:
                return p.cnt > 0
            elif p.right.val <= target:
                p = p.right
            else:
                p = p.down
        return False
            
    def add(self, num: int) -> None:
        p = self.root
        path = []
        while p:
            if p.val == num:
                while p:
                    p.cnt += 1
                    p = p.down
                return
            elif p.right.val <= num:
                p = p.right
            else:
                path.append(p)
                p = p.down
        node = Node(num)
        node.right = path[-1].right
        path[-1].right = node
        path.pop(-1)
        while path and random.random() < 0.5:
            last_level = path.pop(-1)
            new_node = Node(num)
            new_node.right = last_level.right
            last_level.right = new_node
            new_node.down = node
            node = new_node

    def erase(self, target: int) -> bool:
        p = self.root
        while p:
            if p.val == target:
                if p.cnt > 0:
                    while p:
                        p.cnt -= 1
                        p = p.down
                    return True
                else:
                    return False
            elif p.right.val <= target:
                p = p.right
            else:
                p = p.down
        return False


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)


import random
class Node(object):
    def __init__(self, val, right, down, left=None):
        self.val = val
        self.right = right
        self.down = down
        self.left = left
    
    def delete(self):
        self.left.right = self.right
        self.right.left = self.left
        
    def insert(self, val, down):
        node = Node(val, self.right, down, self)
        self.right.left = node
        self.right = node
        return node
        

class Skiplist(object):

    def __init__(self):
        end = Node(20001, None, None)
        self.head = Node(-1, end, None)
        end.left = self.head

    def addLayer(self):
        end = Node(20001, None, None)
        self.head = Node(-1, end, self.head)
        end.left = self.head
        
    def printList(self):
        print(\"=========\")
        #res = []
        head = self.head
        while head is not None:
            line = []
            cur = head
            while cur is not None:
                line.append(cur.val)
                cur = cur.right
            print(line)
            head = head.down
        
        
    def search(self, target):
        \"\"\"
        :type target: int
        :rtype: bool
        \"\"\"
        cur = self.head
        while cur is not None:
            if cur.right.val > target:
                cur = cur.down
            elif cur.right.val == target:
                return True
            else: # cur.next is not None and cur.next.val < target
                cur = cur.right
                
        return False
                

    def add(self, num):
        \"\"\"
        :type num: int
        :rtype: None
        \"\"\"
        cur = self.head
        
        stack = []
        
        while True:
            if cur.right.val <= num:
                cur = cur.right
            elif cur.down is not None:
                stack.append(cur)
                cur = cur.down
            else:
                node = cur.insert(num, None)
                flag = True
                while random.random() > 0.5 and flag:
                    if len(stack) > 0:
                        cur = stack.pop()
                    else:
                        flag = False
                        self.addLayer()
                        cur = self.head
                    #print(\"inserting \",num,\" to the right of \", cur.val)
                    node = cur.insert(num, node)
                break
        #self.printList()
        return False

    def erase(self, num):
        \"\"\"
        :type num: int
        :rtype: bool
        \"\"\"
        cur = self.head
        while cur is not None:
            if cur.right is None or cur.right.val > num:
                cur = cur.down
            elif cur.right.val == num:
                # expand this section
                d = cur.right
                while d is not None:
                    d.delete()
                    d = d.down
                return True
            else: # cur.next is not None and cur.next.val < target
                cur = cur.right
        return False
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

class Node(object):
    
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None

class Skiplist(object):

    def __init__(self):
        self.S = [Node(None)]

    def search(self, target):
        \"\"\"
        :type target: int
        :rtype: bool
        \"\"\"
        curr = self.S[-1]
        while curr:
            # Move right as far as possible without overshooting in the current level 
            while curr.next and curr.next.val <= target:
                if curr.next.val == target:
                    # If target found in some (potentially intermediate) level, exit immediately
                    return True
                curr = curr.next
            # Traversed current level as far as possible without finding target
            # Move one level down to expand search
            curr = curr.down
        # Traversed till the end without finding the target, return False
        return False

    def add(self, num):
        \"\"\"
        :type num: int
        :rtype: None
        \"\"\"
        # Start at the lowest level and keep flipping coins to decide whether
        # to insert an entry for the given value at the next higher level as well.
        k = 1
        p = random.choice([0, 1])
        while (p == 1) and (k < len(self.S)):
            k += 1
            p = random.choice([0, 1])
        if k == len(self.S):
            # If an entry will be inserted at the highest level, expand the number of levels.
            nr = Node(None)
            nr.down = self.S[-1]
            self.S.append(nr)
        curr = self.S[-1]
        kc = len(self.S)
        par = None
        while curr:
            # Traverse to the right in the current level as far as possible without overshooting.
            while curr.next and curr.next.val <= num:
                curr = curr.next
            if kc <= k:
                # An entry for the new value needs to be inserted in the current level.
                # This entry should be inserted just after the point where rightward traversal stopped.
                nn = Node(num)
                nn.next = curr.next
                curr.next = nn
                # Update the downward link for the new entry inserted in the previous level.
                if par:
                    par.down = nn
                par = nn
            # Current level done, keep going down.
            curr = curr.down
            kc -= 1

    def erase(self, num):
        \"\"\"
        :type num: int
        :rtype: bool
        \"\"\"
        curr = self.S[-1]
        res = False
        while curr:
            # Traverse to the right in the current level as far as possible without overshooting.
            while curr.next and curr.next.val <= num:
                if curr.next.val == num:
                    # Target value found inside the next node in the current level.
                    # Delete the next node, and since we're done with the current level now,
                    # break out of the loop and move on to the next level downwards.
                    res = True
                    curr.next = curr.next.next
                    break
                else:
                    curr = curr.next
            # Go one level down and repeat the process.
            curr = curr.down
        # Trim the levels if multiple levels can be found towards the top which have only the dummy terminal entry.
        # Leave only one of them.
        while len(self.S) >= 2:
            cand = self.S[-2]
            if cand.next is None:
                self.S.pop()
            else:
                break
        return res
        


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)