





"""simple docstring"""




from __future__ import annotations

from random import random
from typing import Generic, TypeVar

a						: Any     	=			TypeVar('''KT''')
a						: List[str]     	=			TypeVar('''VT''')


class        __UpperCamelCase				(						Generic[KT, VT]						):






							def __init__(   self      ,					lowerCAmelCase__ = "root"      ,					lowerCAmelCase__ = None      )	-> Dict:
								a      :		List[str]	=				key
								a      :		Dict	=				value
								a      :		list[Node[KT, VT]]	=				[]






							def __repr__(   self      )	-> str:
								return f"""Node({self.key}: {self.value})"""






							@property
							def     __a   (   self      )	-> int:
								return len(self.forward      )


class        __UpperCamelCase				(						Generic[KT, VT]						):






							def __init__(   self      ,					lowerCAmelCase__ = 0.5      ,					lowerCAmelCase__ = 16      )	-> Optional[Any]:
								a      :		Node[KT, VT]	=				Node[KT, VT]()
								a      :		Union[str, Any]	=				0
								a      :		str	=				p
								a      :		List[str]	=				max_level






							def __str__(   self      )	-> str:
								a      :		str	=				list(self      )

								if len(lowerCAmelCase__      ) == 0:
									return f"""SkipList(level={self.level})"""

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

								a      :		Tuple	=				self.head
								a      :		int	=				[]

								a      :		int	=				node.forward.copy()
								lines.append(f"""[{node.key}]""".ljust(lowerCAmelCase__      ,					"-"      ) + "* " * len(lowerCAmelCase__      )      )
								lines.append(" " * label_size + "| " * len(lowerCAmelCase__      )      )

								while len(node.forward      ) != 0:
									a      :		Optional[int]	=				node.forward[0]

									lines.append(
									    f"""[{node.key}]""".ljust(lowerCAmelCase__      ,					"-"      )
									    + " ".join(str(n.key      ) if n.key == node.key else "|" for n in forwards      )      )
									lines.append(" " * label_size + "| " * len(lowerCAmelCase__      )      )
									a      :		Any	=				node.forward

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






							def __iter__(   self      )	-> List[str]:
								a      :		str	=				self.head

								while len(node.forward      ) != 0:
									yield node.forward[0].key
									a      :		Optional[int]	=				node.forward[0]






							def     __a   (   self      )	-> int:
								a      :		str	=				1
								while random() < self.p and level < self.max_level:
									level += 1

								return level






							def     __a   (   self      ,					lowerCAmelCase__      )	-> tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:
								a      :		Optional[int]	=				[]

								a      :		List[str]	=				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      :		Union[str, Any]	=				node.forward[i]
									# Each leftmost node (relative to searched node) will potentially have to
									# be updated.
									update_vector.append(lowerCAmelCase__      )

								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     __a   (   self      ,					lowerCAmelCase__      )	-> int:
								a,       a      :		str	=				self._locate_node(lowerCAmelCase__      )

								if node is not None:
									for i, update_node in enumerate(lowerCAmelCase__      ):
										# 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      :		Any	=				node.forward[i]
											else:
												a      :		List[str]	=				update_node.forward[:i]






							def     __a   (   self      ,					lowerCAmelCase__      ,					lowerCAmelCase__      )	-> Tuple:
								a,       a      :		Optional[Any]	=				self._locate_node(lowerCAmelCase__      )
								if node is not None:
									a      :		int	=				value
								else:
									a      :		Dict	=				self.random_level()

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

									a      :		Tuple	=				Node(lowerCAmelCase__      ,					lowerCAmelCase__      )

									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(lowerCAmelCase__      )
										else:
											a      :		Optional[int]	=				new_node






							def     __a   (   self      ,					lowerCAmelCase__      )	-> VT | None:
								a,       a      :		Any	=				self._locate_node(lowerCAmelCase__      )

								if node is not None:
									return node.value

								return None






def       _SCREAMING_SNAKE_CASE		(	) ->Optional[int]:






	'''simple docstring'''






	a      :		Union[str, Any]	=				SkipList()
	skip_list.insert("Key1"    ,       3					)
	skip_list.insert("Key2"    ,       12					)
	skip_list.insert("Key3"    ,       41					)
	skip_list.insert("Key4"    ,       -19					)

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

	assert len(_lowercase					) == 4
	assert all_values["Key1"] == 3
	assert all_values["Key2"] == 12
	assert all_values["Key3"] == 41
	assert all_values["Key4"] == -19






def       _SCREAMING_SNAKE_CASE		(	) ->Optional[int]:






	'''simple docstring'''






	a      :		Dict	=				SkipList()
	skip_list.insert("Key1"    ,       10					)
	skip_list.insert("Key1"    ,       12					)

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

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

	a      :		int	=				skip_list.head
	a      :		Dict	=				{}
	while node.level != 0:
		a      :		int	=				node.forward[0]
		a      :		List[str]	=				node.value

	if len(_lowercase					) != 4:
		print()
	assert len(_lowercase					) == 4
	assert all_values["Key1"] == 12
	assert all_values["Key7"] == 7
	assert all_values["Key5"] == 5
	assert all_values["Key10"] == 10






def       _SCREAMING_SNAKE_CASE		(	) ->Dict:






	'''simple docstring'''






	a      :		Optional[Any]	=				SkipList()
	assert skip_list.find("Some key"					) is None






def       _SCREAMING_SNAKE_CASE		(	) ->Union[str, Any]:






	'''simple docstring'''






	a      :		List[str]	=				SkipList()

	skip_list.insert("Key2"    ,       20					)
	assert skip_list.find("Key2"					) == 20

	skip_list.insert("Some Key"    ,       10					)
	skip_list.insert("Key2"    ,       8					)
	skip_list.insert("V"    ,       13					)

	assert skip_list.find("Y"					) is None
	assert skip_list.find("Key2"					) == 8
	assert skip_list.find("Some Key"					) == 10
	assert skip_list.find("V"					) == 13






def       _SCREAMING_SNAKE_CASE		(	) ->List[Any]:






	'''simple docstring'''






	a      :		Optional[int]	=				SkipList()
	skip_list.delete("Some key"					)

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






def       _SCREAMING_SNAKE_CASE		(	) ->List[Any]:






	'''simple docstring'''






	a      :		int	=				SkipList()

	skip_list.insert("Key1"    ,       12					)
	skip_list.insert("V"    ,       13					)
	skip_list.insert("X"    ,       14					)
	skip_list.insert("Key2"    ,       15					)

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

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






def       _SCREAMING_SNAKE_CASE		(	) ->int:






	'''simple docstring'''






	a      :		List[Any]	=				SkipList()

	skip_list.insert("Key1"    ,       12					)
	skip_list.insert("V"    ,       13					)
	skip_list.insert("X"    ,       14					)
	skip_list.insert("Key2"    ,       15					)

	skip_list.delete("V"					)
	assert skip_list.find("V"					) is None
	assert skip_list.find("X"					) == 14
	assert skip_list.find("Key1"					) == 12
	assert skip_list.find("Key2"					) == 15

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

	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"					) == 15

	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       _SCREAMING_SNAKE_CASE		(	) ->Optional[int]:






	'''simple docstring'''






	a      :		List[Any]	=				SkipList()

	skip_list.insert("Key1"    ,       12					)
	skip_list.insert("V"    ,       13					)
	skip_list.insert("X"    ,       142					)
	skip_list.insert("Key2"    ,       15					)

	skip_list.delete("X"					)

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

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






def       _SCREAMING_SNAKE_CASE		(	) ->Dict:






	'''simple docstring'''






	def is_sorted(_lowercase						:    List[str]					):
		return all(next_item >= item for item, next_item in zip(_lowercase    ,       lst[1:]					)					)

	a      :		Tuple	=				SkipList()
	for i in range(10					):
		skip_list.insert(_lowercase    ,       _lowercase					)
	assert is_sorted(list(_lowercase					)					)
	skip_list.delete(5					)
	skip_list.delete(8					)
	skip_list.delete(2					)
	assert is_sorted(list(_lowercase					)					)
	skip_list.insert(-12    ,       -12					)
	skip_list.insert(77    ,       77					)
	assert is_sorted(list(_lowercase					)					)






def       _SCREAMING_SNAKE_CASE		(	) ->Tuple:






	'''simple docstring'''






	for _ in range(100					):
		# 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       _SCREAMING_SNAKE_CASE		(	) ->str:






	'''simple docstring'''






	a      :		List[Any]	=				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(_lowercase					)


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		main()




"""simple docstring"""




from __future__ import annotations

from functools import lru_cache
from math import ceil

_A			:       Optional[Any]   		=       1_00

_A			:       Optional[int]   		=       set(range(3, NUM_PRIMES, 2))
primes.add(2)
_A			:       int

for prime in range(3, ceil(NUM_PRIMES**0.5), 2):
   if prime not in primes:
      continue
   primes.difference_update(set(range(prime * prime, NUM_PRIMES, prime)))


@lru_cache(maxsize=100  )
def   __magic_name__	(      __snake_case				:       int  ) ->				set[int]:
       if number_to_partition < 0:
              return set()
       elif number_to_partition == 0:
              return {1}

       lowercase    :				set[int]       		=							set()
       lowercase    :				int
       lowercase    :				int

       for prime in primes:
              if prime > number_to_partition:
                     continue
              for sub in partition(number_to_partition - prime  ):
                     ret.add(sub * prime  )

       return ret


def   __magic_name__	(      __snake_case				:       int = 5000  ) ->				int | None:
       for number_to_partition in range(1     , __snake_case  ):
              if len(partition(__snake_case  )  ) > number_unique_partitions:
                     return number_to_partition
       return None


if __name__ == "__main__":
   print(F"{solution() = }")


