




from __future__ import annotations

from random import random
from typing import Generic, TypeVar

a													=			TypeVar("KT")
a													=			TypeVar("VT")




class       _A				(		Generic[KT, VT]     ):






		def __init__(    self						,		_SCREAMING_SNAKE_CASE = "root"						,		_SCREAMING_SNAKE_CASE = None			):
								_UpperCAmelCase      =			key
								_UpperCAmelCase      =			value
								_UpperCAmelCase      =			[]






		def __repr__(    self			):
								return F"Node({self.key}: {self.value})"






		@property
		def 				UpperCAmelCase (    self			):
								return len(self.forward			)




class       _A				(		Generic[KT, VT]     ):






		def __init__(    self						,		_SCREAMING_SNAKE_CASE = 0.5						,		_SCREAMING_SNAKE_CASE = 16			):
								_UpperCAmelCase      =			Node[KT, VT]()
								_UpperCAmelCase      =			0
								_UpperCAmelCase      =			p
								_UpperCAmelCase      =			max_level






		def __str__(    self			):
								_UpperCAmelCase      =			list(self			)

								if len(_SCREAMING_SNAKE_CASE			) == 0:
														return F"SkipList(level={self.level})"

								_UpperCAmelCase      =			max((len(str(_SCREAMING_SNAKE_CASE			)			) for item in items)						,		default=4			)
								_UpperCAmelCase      =			max(_SCREAMING_SNAKE_CASE						,		4			) + 4

								_UpperCAmelCase      =			self.head
								_UpperCAmelCase      =			[]

								_UpperCAmelCase      =			node.forward.copy()
								lines.append(F"[{node.key}]".ljust(_SCREAMING_SNAKE_CASE						,		"""-"""			) + """* """ * len(_SCREAMING_SNAKE_CASE			)			)
								lines.append(""" """ * label_size + """| """ * len(_SCREAMING_SNAKE_CASE			)			)

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

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

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






		def __iter__(    self			):
								_UpperCAmelCase      =			self.head

								while len(node.forward			) != 0:
														yield node.forward[0].key
														_UpperCAmelCase      =			node.forward[0]






		def 				UpperCAmelCase (    self			):
								_UpperCAmelCase      =			1
								while random() < self.p and level < self.max_level:
														level += 1

								return level






		def 				UpperCAmelCase (    self						,		_SCREAMING_SNAKE_CASE			):
								_UpperCAmelCase      =			[]

								_UpperCAmelCase      =			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:
																				_UpperCAmelCase      =			node.forward[i]
														# Each leftmost node (relative to searched node) will potentially have to
														# be updated.
														update_vector.append(_SCREAMING_SNAKE_CASE			)

								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 				UpperCAmelCase (    self						,		_SCREAMING_SNAKE_CASE			):
								_UpperCAmelCase    ,					_UpperCAmelCase      =			self._locate_node(_SCREAMING_SNAKE_CASE			)

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






		def 				UpperCAmelCase (    self						,		_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE			):
								_UpperCAmelCase    ,					_UpperCAmelCase      =			self._locate_node(_SCREAMING_SNAKE_CASE			)
								if node is not None:
														_UpperCAmelCase      =			value
								else:
														_UpperCAmelCase      =			self.random_level()

														if level > self.level:
																				# After level increase we have to add additional nodes to head.
																				for _ in range(self.level - 1						,		_SCREAMING_SNAKE_CASE			):
																										update_vector.append(self.head			)
																				_UpperCAmelCase      =			level

														_UpperCAmelCase      =			Node(_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE			)

														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(_SCREAMING_SNAKE_CASE			)
																				else:
																										_UpperCAmelCase      =			new_node






		def 				UpperCAmelCase (    self						,		_SCREAMING_SNAKE_CASE			):
								_UpperCAmelCase    ,					_UpperCAmelCase      =			self._locate_node(_SCREAMING_SNAKE_CASE			)

								if node is not None:
														return node.value

								return None




def        _SCREAMING_SNAKE_CASE      (		)						->				Dict:
						_UpperCAmelCase      =			SkipList()
						skip_list.insert("""Key1"""			,     3       )
						skip_list.insert("""Key2"""			,     1_2       )
						skip_list.insert("""Key3"""			,     4_1       )
						skip_list.insert("""Key4"""			,     -1_9       )

						_UpperCAmelCase      =			skip_list.head
						_UpperCAmelCase      =			{}
						while node.level != 0:
												_UpperCAmelCase      =			node.forward[0]
												_UpperCAmelCase      =			node.value

						assert len(_UpperCamelCase       ) == 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        _SCREAMING_SNAKE_CASE      (		)						->				Optional[Any]:
						_UpperCAmelCase      =			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       )

						_UpperCAmelCase      =			skip_list.head
						_UpperCAmelCase      =			{}
						while node.level != 0:
												_UpperCAmelCase      =			node.forward[0]
												_UpperCAmelCase      =			node.value

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




def        _SCREAMING_SNAKE_CASE      (		)						->				Tuple:
						_UpperCAmelCase      =			SkipList()
						assert skip_list.find("""Some key"""       ) is None




def        _SCREAMING_SNAKE_CASE      (		)						->				Optional[int]:
						_UpperCAmelCase      =			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        _SCREAMING_SNAKE_CASE      (		)						->				Optional[Any]:
						_UpperCAmelCase      =			SkipList()
						skip_list.delete("""Some key"""       )

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




def        _SCREAMING_SNAKE_CASE      (		)						->				int:
						_UpperCAmelCase      =			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        _SCREAMING_SNAKE_CASE      (		)						->				Any:
						_UpperCAmelCase      =			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        _SCREAMING_SNAKE_CASE      (		)						->				Tuple:
						_UpperCAmelCase      =			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(snake_case       ):
												yield node.key
												for forward_node in node.forward:
																		yield from traverse_keys(_UpperCamelCase       )

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




def        _SCREAMING_SNAKE_CASE      (		)						->				List[Any]:






						def is_sorted(snake_case       ):
												return all(next_item >= item for item, next_item in zip(_UpperCamelCase			,     lst[1:]       )       )

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




def        _SCREAMING_SNAKE_CASE      (		)						->				Dict:






						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        _SCREAMING_SNAKE_CASE      (		)						->				Union[str, Any]:
						_UpperCAmelCase      =			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(_UpperCamelCase       )


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				main()





from __future__ import annotations




def        _SCREAMING_SNAKE_CASE      (		snake_case			,     snake_case       )						->				float:
						_UpperCAmelCase      =			sorted(numsa + numsa       )
						_UpperCAmelCase    ,					_UpperCAmelCase      =			divmod(len(snake_case       )			,     2       )
						if mod == 1:
												return all_numbers[div]
						else:
												return (all_numbers[div] + all_numbers[div - 1]) / 2


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				a													=			[float(x) for x in input("Enter the elements of first array: ").split()]
				a													=			[float(x) for x in input("Enter the elements of second array: ").split()]
				print(F'The median of two arrays is: {median_of_two_arrays(array_a, array_a)}')