





"""simple docstring"""




class 				_a		:






				def __init__(				self	:					List[Any],				lowerCAmelCase__	:					Any							)			->   Dict:




										'''simple docstring'''



										_UpperCamelCase    :      Optional[Any]						     =					val
										# Number of nodes in left subtree
										_UpperCamelCase    :      str						     =					0
										_UpperCamelCase    :      Optional[int]						     =					None
										_UpperCamelCase    :      Union[str, Any]						     =					None
										_UpperCamelCase    :      Dict						     =					None






				def        snake_case			(				self	:					List[str],				lowerCAmelCase__	:					List[str]							)			->   List[Any]:




										'''simple docstring'''



										assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

										if self.val < other.val:
																_UpperCamelCase    :      Any						     =					self.right
																_UpperCamelCase    :      List[Any]						     =					None
																if self.right:
																						_UpperCamelCase    :      List[str]						     =					other
																_UpperCamelCase    :      Optional[Any]						     =					other
																_UpperCamelCase    :      int						     =					self.left_tree_size * 2 + 1
																return self
										else:
																_UpperCamelCase    :      Optional[Any]						     =					other.right
																_UpperCamelCase    :      str						     =					None
																if other.right:
																						_UpperCamelCase    :      Dict						     =					self
																_UpperCamelCase    :      Tuple						     =					self
																_UpperCamelCase    :      Tuple						     =					other.left_tree_size * 2 + 1
																return other




class 				_a		:






				def __init__(				self	:					List[str],				lowerCAmelCase__	:					Union[str, Any]=None,				lowerCAmelCase__	:					Union[str, Any]=None,				lowerCAmelCase__	:					Union[str, Any]=0							)			->   str:




										'''simple docstring'''



										_UpperCamelCase    :      Tuple						     =					heap_size
										_UpperCamelCase    :      str						     =					bottom_root
										_UpperCamelCase    :      Optional[int]						     =					min_node






				def        snake_case			(				self	:					List[str],				lowerCAmelCase__	:					Tuple							)			->   Optional[int]:




										'''simple docstring'''



										if other.size == 0:
																return None
										if self.size == 0:
																_UpperCamelCase    :      List[Any]						     =					other.size
																_UpperCamelCase    :      Union[str, Any]						     =					other.bottom_root
																_UpperCamelCase    :      List[str]						     =					other.min_node
																return None
										# Update size
										_UpperCamelCase    :      Dict						     =					self.size + other.size

										# Update min.node
										if self.min_node.val > other.min_node.val:
																_UpperCamelCase    :      Dict						     =					other.min_node
										# Merge

										# Order roots by left_subtree_size
										_UpperCamelCase    :      int						     =					[]
										_UpperCamelCase     ,							_UpperCamelCase    :      Union[str, Any]						     =					self.bottom_root, other.bottom_root
										while i or j:
																if i and ((not j) or i.left_tree_size < j.left_tree_size):
																						combined_roots_list.append((i, True)							)
																						_UpperCamelCase    :      Tuple						     =					i.parent
																else:
																						combined_roots_list.append((j, False)							)
																						_UpperCamelCase    :      Union[str, Any]						     =					j.parent
        # Insert links between them
										for i in range(len(lowerCAmelCase__							) - 1							):
																if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
																						_UpperCamelCase    :      List[Any]						     =					combined_roots_list[i + 1][0]
																						_UpperCamelCase    :      str						     =					combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
										_UpperCamelCase    :      List[str]						     =					combined_roots_list[0][0]
										while i.parent:
																if (
																    (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
																) or (
																    i.left_tree_size == i.parent.left_tree_size
																    and i.left_tree_size != i.parent.parent.left_tree_size
																):
																						# Neighbouring Nodes
																						_UpperCamelCase    :      str						     =					i.left
																						_UpperCamelCase    :      int						     =					i.parent.parent

																						# Merging trees
																						_UpperCamelCase    :      Optional[Any]						     =					i.merge_trees(i.parent							)

																						# Updating links
																						_UpperCamelCase    :      Optional[int]						     =					previous_node
																						_UpperCamelCase    :      List[Any]						     =					next_node
																						if previous_node:
																												_UpperCamelCase    :      Optional[int]						     =					i
																						if next_node:
																												_UpperCamelCase    :      Tuple						     =					i
																else:
																						_UpperCamelCase    :      Any						     =					i.parent
        # Updating self.bottom_root
										while i.left:
																_UpperCamelCase    :      Optional[Any]						     =					i.left
										_UpperCamelCase    :      Dict						     =					i

										# Update other
										_UpperCamelCase    :      Dict						     =					self.size
										_UpperCamelCase    :      Dict						     =					self.bottom_root
										_UpperCamelCase    :      int						     =					self.min_node

										# Return the merged heap
										return self






				def        snake_case			(				self	:					Union[str, Any],				lowerCAmelCase__	:					List[Any]							)			->   Dict:




										'''simple docstring'''



										if self.size == 0:
																_UpperCamelCase    :      Tuple						     =					Node(lowerCAmelCase__							)
																_UpperCamelCase    :      List[str]						     =					1
																_UpperCamelCase    :      Optional[int]						     =					self.bottom_root
										else:
																# Create new node
																_UpperCamelCase    :      str						     =					Node(lowerCAmelCase__							)

																# Update size
																self.size += 1

																# update min_node
																if val < self.min_node.val:
																						_UpperCamelCase    :      Optional[int]						     =					new_node
																# Put new_node as a bottom_root in heap
																_UpperCamelCase    :      int						     =					new_node
																_UpperCamelCase    :      Optional[Any]						     =					self.bottom_root
																_UpperCamelCase    :      Any						     =					new_node

																# Consecutively merge roots with same left_tree_size
																while (
																    self.bottom_root.parent
																    and self.bottom_root.left_tree_size
																    == self.bottom_root.parent.left_tree_size
																):
																						# Next node
																						_UpperCamelCase    :      List[Any]						     =					self.bottom_root.parent.parent

																						# Merge
																						_UpperCamelCase    :      Optional[Any]						     =					self.bottom_root.merge_trees(self.bottom_root.parent							)

																						# Update Links
																						_UpperCamelCase    :      Optional[int]						     =					next_node
																						_UpperCamelCase    :      Union[str, Any]						     =					None
																						if next_node:
																												_UpperCamelCase    :      Dict						     =					self.bottom_root






				def        snake_case			(				self	:					Dict							)			->   int:




										'''simple docstring'''



										return self.min_node.val






				def        snake_case			(				self	:					List[str]							)			->   List[str]:




										'''simple docstring'''



										return self.size == 0






				def        snake_case			(				self	:					Any							)			->   int:




										'''simple docstring'''



										_UpperCamelCase    :      Dict						     =					self.min_node.val

										# Last element in heap corner case
										if self.size == 1:
																# Update size
																_UpperCamelCase    :      List[Any]						     =					0

																# Update bottom root
																_UpperCamelCase    :      List[Any]						     =					None

																# Update min_node
																_UpperCamelCase    :      Tuple						     =					None

																return min_value
										# No right subtree corner case
										# The structure of the tree implies that this should be the bottom root
										# and there is at least one other root
										if self.min_node.right is None:
																# Update size
																self.size -= 1

																# Update bottom root
																_UpperCamelCase    :      Dict						     =					self.bottom_root.parent
																_UpperCamelCase    :      Dict						     =					None

																# Update min_node
																_UpperCamelCase    :      List[Any]						     =					self.bottom_root
																_UpperCamelCase    :      Optional[int]						     =					self.bottom_root.parent
																while i:
																						if i.val < self.min_node.val:
																												_UpperCamelCase    :      Union[str, Any]						     =					i
																						_UpperCamelCase    :      Any						     =					i.parent
																return min_value
										# General case
										# Find the BinomialHeap of the right subtree of min_node
										_UpperCamelCase    :      List[str]						     =					self.min_node.right
										_UpperCamelCase    :      str						     =					None
										_UpperCamelCase    :      List[Any]						     =					bottom_of_new
										_UpperCamelCase    :      Optional[int]						     =					1

										# Size, min_node and bottom_root
										while bottom_of_new.left:
																_UpperCamelCase    :      int						     =					size_of_new * 2 + 1
																_UpperCamelCase    :      Dict						     =					bottom_of_new.left
																if bottom_of_new.val < min_of_new.val:
																						_UpperCamelCase    :      str						     =					bottom_of_new
        # Corner case of single root on top left path
										if (not self.min_node.left) and (not self.min_node.parent):
																_UpperCamelCase    :      Any						     =					size_of_new
																_UpperCamelCase    :      Optional[Any]						     =					bottom_of_new
																_UpperCamelCase    :      List[str]						     =					min_of_new
																# print("Single root, multiple nodes case")
																return min_value
										# Remaining cases
										# Construct heap of right subtree
										_UpperCamelCase    :      Tuple						     =					BinomialHeap(
										    bottom_root=lowerCAmelCase__,				min_node=lowerCAmelCase__,				heap_size=lowerCAmelCase__							)

										# Update size
										_UpperCamelCase    :      Optional[Any]						     =					self.size - 1 - size_of_new

										# Neighbour nodes
										_UpperCamelCase    :      Dict						     =					self.min_node.left
										_UpperCamelCase    :      str						     =					self.min_node.parent

										# Initialize new bottom_root and min_node
										_UpperCamelCase    :      int						     =					previous_node or next_node
										_UpperCamelCase    :      List[str]						     =					next_node

										# Update links of previous_node and search below for new min_node and
										# bottom_root
										if previous_node:
																_UpperCamelCase    :      Union[str, Any]						     =					next_node

																# Update bottom_root and search for min_node below
																_UpperCamelCase    :      Tuple						     =					previous_node
																_UpperCamelCase    :      Union[str, Any]						     =					previous_node
																while self.bottom_root.left:
																						_UpperCamelCase    :      Union[str, Any]						     =					self.bottom_root.left
																						if self.bottom_root.val < self.min_node.val:
																												_UpperCamelCase    :      Union[str, Any]						     =					self.bottom_root
										if next_node:
																_UpperCamelCase    :      List[str]						     =					previous_node

																# Search for new min_node above min_node
																_UpperCamelCase    :      str						     =					next_node
																while i:
																						if i.val < self.min_node.val:
																												_UpperCamelCase    :      Optional[int]						     =					i
																						_UpperCamelCase    :      int						     =					i.parent
        # Merge heaps
										self.merge_heaps(lowerCAmelCase__							)

										return min_value






				def        snake_case			(				self	:					Any							)			->   int:




										'''simple docstring'''



										_UpperCamelCase    :      Union[str, Any]						     =					self.bottom_root
										while top_root.parent:
																_UpperCamelCase    :      int						     =					top_root.parent
										# preorder
										_UpperCamelCase    :      Any						     =					[]
										self.__traversal(lowerCAmelCase__,				lowerCAmelCase__							)
										return heap_pre_order






				def        snake_case			(				self	:					Optional[Any],				lowerCAmelCase__	:					int,				lowerCAmelCase__	:					int,				lowerCAmelCase__	:					Union[str, Any]=0							)			->   Optional[Any]:




										'''simple docstring'''



										if curr_node:
																preorder.append((curr_node.val, level)							)
																self.__traversal(curr_node.left,				lowerCAmelCase__,				level + 1							)
																self.__traversal(curr_node.right,				lowerCAmelCase__,				level + 1							)
										else:
																preorder.append(('''#''', level)							)






				def __str__(				self	:					List[Any]							)			->   Optional[int]:




										'''simple docstring'''



										if self.is_empty():
																return ""
										_UpperCamelCase    :      str						     =					self.pre_order()

										return "\n".join(('''-''' * level + str(lowerCAmelCase__							)) for value, level in preorder_heap							)


# Unit Tests
if __name__ == "__main__":
						import doctest

						doctest.testmod()










"""simple docstring"""




def  a_       (							_lowercase ,		_lowercase     ):
						sequence.append(_lowercase     )

						_UpperCamelCase    :      int						     =					0
						while sequence[index] != target:
												index += 1

						sequence.pop()

						if index == len(_lowercase     ):
												return None

						return index


if __name__ == "__main__":
						UpperCamelCase_     =input("""Enter numbers separated by comma:\n""").strip()
						UpperCamelCase_     =[int(item) for item in user_input.split(""",""")]

						UpperCamelCase_     =input("""Enter a single number to be found in the list:\n""")
						UpperCamelCase_     =int(target_input)
						UpperCamelCase_     =sentinel_linear_search(sequence, target)
						if result is not None:
												print(F"{target} found at positions: {result}")
						else:
												print("""Not found""")



