



from __future__ import annotations

from random import random
from typing import Generic, TypeVar

lowercase__			   =  TypeVar("KT")
lowercase__			   =  TypeVar("VT")




class SCREAMING_SNAKE_CASE__					(		Generic[KT, VT]      ):



						def __init__(self						,     _lowercase = "root"						,     _lowercase = None							):





													'''simple docstring'''

													__a		:		List[str]									=       key
													__a		:		Tuple									=       value
													__a		:		list[Node[KT, VT]]									=       []



						def __repr__(self							):





													'''simple docstring'''

													return F'''Node({self.key}: {self.value})'''





						@property
						def     lowerCAmelCase__(self							):





													'''simple docstring'''

													return len(self.forward							)







class SCREAMING_SNAKE_CASE__					(		Generic[KT, VT]      ):



						def __init__(self						,     _lowercase = 0.5						,     _lowercase = 16							):





													'''simple docstring'''

													__a		:		Node[KT, VT]									=       Node[KT, VT]()
													__a		:		Tuple									=       0
													__a		:		Tuple									=       p
													__a		:		List[Any]									=       max_level



						def __str__(self							):





													'''simple docstring'''

													__a		:		Optional[Any]									=       list(self							)

													if len(_lowercase							) == 0:
																				return F'''SkipList(level={self.level})'''

													__a		:		List[str]									=       max((len(str(_lowercase							)							) for item in items)						,     default=4							)
													__a		:		List[Any]									=       max(_lowercase						,     4							) + 4

													__a		:		List[str]									=       self.head
													__a		:		List[str]									=       []

													__a		:		Optional[Any]									=       node.forward.copy()
													lines.append(F'''[{node.key}]'''.ljust(_lowercase						,     """-"""							) + """* """ * len(_lowercase							)							)
													lines.append(""" """ * label_size + """| """ * len(_lowercase							)							)

													while len(node.forward							) != 0:
																				__a		:		Tuple									=       node.forward[0]

																				lines.append(
																				    F'''[{node.key}]'''.ljust(_lowercase						,     """-"""							)
																				    + """ """.join(str(n.key							) if n.key == node.key else """|""" for n in forwards							)							)
																				lines.append(""" """ * label_size + """| """ * len(_lowercase							)							)
																				__a		:		Tuple									=       node.forward

													lines.append("""None""".ljust(_lowercase							) + """* """ * len(_lowercase							)							)
													return F'''SkipList(level={self.level})\n''' + "\n".join(_lowercase							)



						def __iter__(self							):





													'''simple docstring'''

													__a		:		int									=       self.head

													while len(node.forward							) != 0:
																				yield node.forward[0].key
																				__a		:		List[Any]									=       node.forward[0]



						def     lowerCAmelCase__(self							):





													'''simple docstring'''

													__a		:		Any									=       1
													while random() < self.p and level < self.max_level:
																				level += 1

													return level



						def     lowerCAmelCase__(self						,     _lowercase							):





													'''simple docstring'''

													__a		:		List[str]									=       []

													__a		:		int									=       self.head

													for i in reversed(range(self.level							)							):
																				# i < node.level - When node level is lesser than `i` decrement `i`.
																				# node.forward[i].key < key - Jumping to node with key value higher
																				#                             or equal to searched key would result
																				#                             in skipping searched key.
																				while i < node.level and node.forward[i].key < key:
																											__a		:		List[str]									=       node.forward[i]
																				# Each leftmost node (relative to searched node) will potentially have to
																				# be updated.
																				update_vector.append(_lowercase							)

													update_vector.reverse()  # Note that we were inserting values in reverse order.

													# len(node.forward) != 0 - If current node doesn't contain any further
													#                          references then searched key is not present.
													# node.forward[0].key == key - Next node key should be equal to search key
													#                              if key is present.
													if len(node.forward							) != 0 and node.forward[0].key == key:
																				return node.forward[0], update_vector
													else:
																				return None, update_vector



						def     lowerCAmelCase__(self						,     _lowercase							):





													'''simple docstring'''

													__a		:		Dict									=       self._locate_node(_lowercase							)

													if node is not None:
																				for i, update_node in enumerate(_lowercase							):
																											# Remove or replace all references to removed node.
																											if update_node.level > i and update_node.forward[i].key == key:
																																		if node.level > i:
																																									__a		:		str									=       node.forward[i]
																																		else:
																																									__a		:		List[str]									=       update_node.forward[:i]



						def     lowerCAmelCase__(self						,     _lowercase						,     _lowercase							):





													'''simple docstring'''

													__a		:		List[str]									=       self._locate_node(_lowercase							)
													if node is not None:
																				__a		:		Union[str, Any]									=       value
													else:
																				__a		:		int									=       self.random_level()

																				if level > self.level:
																											# After level increase we have to add additional nodes to head.
																											for _ in range(self.level - 1						,     _lowercase							):
																																		update_vector.append(self.head							)
																											__a		:		List[Any]									=       level

																				__a		:		List[Any]									=       Node(_lowercase						,     _lowercase							)

																				for i, update_node in enumerate(update_vector[:level]							):
																											# Change references to pass through new node.
																											if update_node.level > i:
																																		new_node.forward.append(update_node.forward[i]							)

																											if update_node.level < i + 1:
																																		update_node.forward.append(_lowercase							)
																											else:
																																		__a		:		Any									=       new_node





						def     lowerCAmelCase__(self						,     _lowercase							):





													'''simple docstring'''

													__a		:		List[str]									=       self._locate_node(_lowercase							)

													if node is not None:
																				return node.value

													return None







def       __magic_name__    (   ):
							__a		:		Tuple									=       SkipList()
							skip_list.insert("""Key1"""  ,       3					)
							skip_list.insert("""Key2"""  ,       1_2					)
							skip_list.insert("""Key3"""  ,       4_1					)
							skip_list.insert("""Key4"""  ,       -1_9					)

							__a		:		Optional[int]									=       skip_list.head
							__a		:		Optional[Any]									=       {}
							while node.level != 0:
														__a		:		int									=       node.forward[0]
														__a		:		Any									=       node.value

							assert len(SCREAMING_SNAKE_CASE_					) == 4
							assert all_values["Key1"] == 3
							assert all_values["Key2"] == 1_2
							assert all_values["Key3"] == 4_1
							assert all_values["Key4"] == -1_9





def       __magic_name__    (   ):
							__a		:		int									=       SkipList()
							skip_list.insert("""Key1"""  ,       1_0					)
							skip_list.insert("""Key1"""  ,       1_2					)

							skip_list.insert("""Key5"""  ,       7					)
							skip_list.insert("""Key7"""  ,       1_0					)
							skip_list.insert("""Key10"""  ,       5					)

							skip_list.insert("""Key7"""  ,       7					)
							skip_list.insert("""Key5"""  ,       5					)
							skip_list.insert("""Key10"""  ,       1_0					)

							__a		:		Union[str, Any]									=       skip_list.head
							__a		:		Tuple									=       {}
							while node.level != 0:
														__a		:		List[Any]									=       node.forward[0]
														__a		:		int									=       node.value

							if len(SCREAMING_SNAKE_CASE_					) != 4:
														print()
							assert len(SCREAMING_SNAKE_CASE_					) == 4
							assert all_values["Key1"] == 1_2
							assert all_values["Key7"] == 7
							assert all_values["Key5"] == 5
							assert all_values["Key10"] == 1_0





def       __magic_name__    (   ):
							__a		:		int									=       SkipList()
							assert skip_list.find("""Some key"""					) is None





def       __magic_name__    (   ):
							__a		:		Optional[int]									=       SkipList()

							skip_list.insert("""Key2"""  ,       2_0					)
							assert skip_list.find("""Key2"""					) == 2_0

							skip_list.insert("""Some Key"""  ,       1_0					)
							skip_list.insert("""Key2"""  ,       8					)
							skip_list.insert("""V"""  ,       1_3					)

							assert skip_list.find("""Y"""					) is None
							assert skip_list.find("""Key2"""					) == 8
							assert skip_list.find("""Some Key"""					) == 1_0
							assert skip_list.find("""V"""					) == 1_3





def       __magic_name__    (   ):
							__a		:		Any									=       SkipList()
							skip_list.delete("""Some key"""					)

							assert len(skip_list.head.forward					) == 0





def       __magic_name__    (   ):
							__a		:		Optional[Any]									=       SkipList()

							skip_list.insert("""Key1"""  ,       1_2					)
							skip_list.insert("""V"""  ,       1_3					)
							skip_list.insert("""X"""  ,       1_4					)
							skip_list.insert("""Key2"""  ,       1_5					)

							skip_list.delete("""V"""					)
							skip_list.delete("""Key2"""					)

							assert skip_list.find("""V"""					) is None
							assert skip_list.find("""Key2"""					) is None





def       __magic_name__    (   ):
							__a		:		Union[str, Any]									=       SkipList()

							skip_list.insert("""Key1"""  ,       1_2					)
							skip_list.insert("""V"""  ,       1_3					)
							skip_list.insert("""X"""  ,       1_4					)
							skip_list.insert("""Key2"""  ,       1_5					)

							skip_list.delete("""V"""					)
							assert skip_list.find("""V"""					) is None
							assert skip_list.find("""X"""					) == 1_4
							assert skip_list.find("""Key1"""					) == 1_2
							assert skip_list.find("""Key2"""					) == 1_5

							skip_list.delete("""X"""					)
							assert skip_list.find("""V"""					) is None
							assert skip_list.find("""X"""					) is None
							assert skip_list.find("""Key1"""					) == 1_2
							assert skip_list.find("""Key2"""					) == 1_5

							skip_list.delete("""Key1"""					)
							assert skip_list.find("""V"""					) is None
							assert skip_list.find("""X"""					) is None
							assert skip_list.find("""Key1"""					) is None
							assert skip_list.find("""Key2"""					) == 1_5

							skip_list.delete("""Key2"""					)
							assert skip_list.find("""V"""					) is None
							assert skip_list.find("""X"""					) is None
							assert skip_list.find("""Key1"""					) is None
							assert skip_list.find("""Key2"""					) is None





def       __magic_name__    (   ):
							__a		:		List[Any]									=       SkipList()

							skip_list.insert("""Key1"""  ,       1_2					)
							skip_list.insert("""V"""  ,       1_3					)
							skip_list.insert("""X"""  ,       1_4_2					)
							skip_list.insert("""Key2"""  ,       1_5					)

							skip_list.delete("""X"""					)

							def traverse_keys(_lowerCamelCase				: List[str]					):
														yield node.key
														for forward_node in node.forward:
																					yield from traverse_keys(SCREAMING_SNAKE_CASE_					)

							assert len(set(traverse_keys(skip_list.head					)					)					) == 4





def       __magic_name__    (   ):
							def is_sorted(_lowerCamelCase				: int					):
														return all(next_item >= item for item, next_item in zip(SCREAMING_SNAKE_CASE_  ,       lst[1:]					)					)

							__a		:		int									=       SkipList()
							for i in range(1_0					):
														skip_list.insert(SCREAMING_SNAKE_CASE_  ,       SCREAMING_SNAKE_CASE_					)
							assert is_sorted(list(SCREAMING_SNAKE_CASE_					)					)
							skip_list.delete(5					)
							skip_list.delete(8					)
							skip_list.delete(2					)
							assert is_sorted(list(SCREAMING_SNAKE_CASE_					)					)
							skip_list.insert(-1_2  ,       -1_2					)
							skip_list.insert(7_7  ,       7_7					)
							assert is_sorted(list(SCREAMING_SNAKE_CASE_					)					)





def       __magic_name__    (   ):
							for _ in range(1_0_0					):
														# Repeat test 100 times due to the probabilistic nature of skip list
														# random values == random bugs
														test_insert()
														test_insert_overrides_existing_value()

														test_searching_empty_list_returns_none()
														test_search()

														test_deleting_item_from_empty_list_do_nothing()
														test_deleted_items_are_not_founded_by_find_method()
														test_delete_removes_only_given_key()
														test_delete_doesnt_leave_dead_nodes()

														test_iter_always_yields_sorted_values()





def       __magic_name__    (   ):
							__a		:		int									=       SkipList()
							skip_list.insert(2  ,       """2"""					)
							skip_list.insert(4  ,       """4"""					)
							skip_list.insert(6  ,       """4"""					)
							skip_list.insert(4  ,       """5"""					)
							skip_list.insert(8  ,       """4"""					)
							skip_list.insert(9  ,       """4"""					)

							skip_list.delete(4					)

							print(SCREAMING_SNAKE_CASE_					)


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	main()






"""simple docstring"""

def       __magic_name__    (   _lowerCamelCase				: list[int]					):
							if not nums:  # Makes sure that the list is not empty
														raise ValueError("""List is empty"""					)

							__a		:		Any									=       sum(_lowerCamelCase					) / len(_lowerCamelCase					)  # Calculate the average
							return sum(abs(x - average					) for x in nums					) / len(_lowerCamelCase					)


if __name__ == "__main__":
	import doctest

	doctest.testmod()

