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.

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

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


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:

	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

	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

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

	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

	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


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:
	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:
		curr = self.heads[-1]
		while curr:
			while curr.__next__ and curr.next.val < target:
				curr = curr.__next__
			if curr.__next__ and curr.next.val == target:
				return True
			curr = curr.down
		return False

	def add(self, num: int) -> None:
		if not self.heads:
			head = Node(-1, Node(num, None, None), None)
			self.heads.append(head)
			self.level = 1
			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)
		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

	def erase(self, num: int) -> bool:
		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
		return seen


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


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


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


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


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]

	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:
			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:
				start.next = start.next.__next__
				start = start.down
			elif start.val < num < start.next.val:
				start = start.down
			else:
				start = start.__next__
		return True


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


import random

class Node:

	def __init__(self, val, level, count=1):
		self.val = val
		self.next = [None] * (level + 1)
		self.count = count

class Skiplist:

	def __init__(self, p=0.5):
		self.p = p
		self.head = Node(None, 0)
		self.levels = 1

	def _randomLevel(self):
		_level = 0
		while random.random() < self.p:
			_level += 1
		return _level

	def _update(self, val):
		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 = self._search(val)
		if node is not None:
			node.count += 1
		else:
			node = Node(val, self._randomLevel())
			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: 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:
				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


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


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


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)
		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:
					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


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)


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:
		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:
		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
		(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]

	def erase(self, num: int) -> bool:
		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 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]
		return True


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:]):
			c.down = n

	def search(self, target) -> bool:
		curr = self.heads[0]
		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 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


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


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


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