



"""simple docstring"""


class    A_    :



						"""simple docstring"""






						def __init__(      self				:Tuple     ,						lowercase_				:int      )       ->    Any:
												UpperCAmelCase    =				val
												# Number of nodes in left subtree
												UpperCAmelCase    =				0
												UpperCAmelCase    =				None
												UpperCAmelCase    =				None
												UpperCAmelCase    =				None






						def 			UpperCAmelCase__  (      self				:Any     ,						lowercase_				:Optional[int]      )       ->    Optional[int]:
												assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

												if self.val < other.val:
																		UpperCAmelCase    =				self.right
																		UpperCAmelCase    =				None
																		if self.right:
																								UpperCAmelCase    =				other
																		UpperCAmelCase    =				other
																		UpperCAmelCase    =				self.left_tree_size * 2 + 1
																		return self
												else:
																		UpperCAmelCase    =				other.right
																		UpperCAmelCase    =				None
																		if other.right:
																								UpperCAmelCase    =				self
																		UpperCAmelCase    =				self
																		UpperCAmelCase    =				other.left_tree_size * 2 + 1
																		return other







class    A_    :



						"""simple docstring"""






						def __init__(      self				:Union[str, Any]     ,						lowercase_				:Optional[Any]=None     ,						lowercase_				:Any=None     ,						lowercase_				:Union[str, Any]=0      )       ->    Any:
												UpperCAmelCase    =				heap_size
												UpperCAmelCase    =				bottom_root
												UpperCAmelCase    =				min_node






						def 			UpperCAmelCase__  (      self				:List[str]     ,						lowercase_				:Dict      )       ->    Dict:

												# Empty heaps corner cases
												if other.size == 0:
																		return None
												if self.size == 0:
																		UpperCAmelCase    =				other.size
																		UpperCAmelCase    =				other.bottom_root
																		UpperCAmelCase    =				other.min_node
																		return None
												# Update size
												UpperCAmelCase    =				self.size + other.size

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

												# Order roots by left_subtree_size
												UpperCAmelCase    =				[]
												UpperCAmelCase   ,					UpperCAmelCase    =				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    =				i.parent
																		else:
																								combined_roots_list.append((j, False)      )
																								UpperCAmelCase    =				j.parent
        # Insert links between them
												for i in range(len(lowercase_      ) - 1      ):
																		if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
																								UpperCAmelCase    =				combined_roots_list[i + 1][0]
																								UpperCAmelCase    =				combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
												UpperCAmelCase    =				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    =				i.left
																								UpperCAmelCase    =				i.parent.parent

																								# Merging trees
																								UpperCAmelCase    =				i.merge_trees(i.parent      )

																								# Updating links
																								UpperCAmelCase    =				previous_node
																								UpperCAmelCase    =				next_node
																								if previous_node:
																														UpperCAmelCase    =				i
																								if next_node:
																														UpperCAmelCase    =				i
																		else:
																								UpperCAmelCase    =				i.parent
        # Updating self.bottom_root
												while i.left:
																		UpperCAmelCase    =				i.left
												UpperCAmelCase    =				i

												# Update other
												UpperCAmelCase    =				self.size
												UpperCAmelCase    =				self.bottom_root
												UpperCAmelCase    =				self.min_node

												# Return the merged heap
												return self






						def 			UpperCAmelCase__  (      self				:List[str]     ,						lowercase_				:Union[str, Any]      )       ->    Union[str, Any]:
												if self.size == 0:
																		UpperCAmelCase    =				Node(lowercase_      )
																		UpperCAmelCase    =				1
																		UpperCAmelCase    =				self.bottom_root
												else:
																		# Create new node
																		UpperCAmelCase    =				Node(lowercase_      )

																		# Update size
																		self.size += 1

																		# update min_node
																		if val < self.min_node.val:
																								UpperCAmelCase    =				new_node
																		# Put new_node as a bottom_root in heap
																		UpperCAmelCase    =				new_node
																		UpperCAmelCase    =				self.bottom_root
																		UpperCAmelCase    =				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    =				self.bottom_root.parent.parent

																								# Merge
																								UpperCAmelCase    =				self.bottom_root.merge_trees(self.bottom_root.parent      )

																								# Update Links
																								UpperCAmelCase    =				next_node
																								UpperCAmelCase    =				None
																								if next_node:
																														UpperCAmelCase    =				self.bottom_root






						def 			UpperCAmelCase__  (      self				:Optional[int]      )       ->    Optional[Any]:
												return self.min_node.val






						def 			UpperCAmelCase__  (      self				:List[str]      )       ->    str:
												return self.size == 0






						def 			UpperCAmelCase__  (      self				:Dict      )       ->    List[Any]:
												UpperCAmelCase    =				self.min_node.val

												# Last element in heap corner case
												if self.size == 1:
																		# Update size
																		UpperCAmelCase    =				0

																		# Update bottom root
																		UpperCAmelCase    =				None

																		# Update min_node
																		UpperCAmelCase    =				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    =				self.bottom_root.parent
																		UpperCAmelCase    =				None

																		# Update min_node
																		UpperCAmelCase    =				self.bottom_root
																		UpperCAmelCase    =				self.bottom_root.parent
																		while i:
																								if i.val < self.min_node.val:
																														UpperCAmelCase    =				i
																								UpperCAmelCase    =				i.parent
																		return min_value
												# General case
												# Find the BinomialHeap of the right subtree of min_node
												UpperCAmelCase    =				self.min_node.right
												UpperCAmelCase    =				None
												UpperCAmelCase    =				bottom_of_new
												UpperCAmelCase    =				1

												# Size, min_node and bottom_root
												while bottom_of_new.left:
																		UpperCAmelCase    =				size_of_new * 2 + 1
																		UpperCAmelCase    =				bottom_of_new.left
																		if bottom_of_new.val < min_of_new.val:
																								UpperCAmelCase    =				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    =				size_of_new
																		UpperCAmelCase    =				bottom_of_new
																		UpperCAmelCase    =				min_of_new
																		# print("Single root, multiple nodes case")
																		return min_value
												# Remaining cases
												# Construct heap of right subtree
												UpperCAmelCase    =				BinomialHeap(
												    bottom_root=lowercase_     ,						min_node=lowercase_     ,						heap_size=lowercase_      )

												# Update size
												UpperCAmelCase    =				self.size - 1 - size_of_new

												# Neighbour nodes
												UpperCAmelCase    =				self.min_node.left
												UpperCAmelCase    =				self.min_node.parent

												# Initialize new bottom_root and min_node
												UpperCAmelCase    =				previous_node or next_node
												UpperCAmelCase    =				next_node

												# Update links of previous_node and search below for new min_node and
												# bottom_root
												if previous_node:
																		UpperCAmelCase    =				next_node

																		# Update bottom_root and search for min_node below
																		UpperCAmelCase    =				previous_node
																		UpperCAmelCase    =				previous_node
																		while self.bottom_root.left:
																								UpperCAmelCase    =				self.bottom_root.left
																								if self.bottom_root.val < self.min_node.val:
																														UpperCAmelCase    =				self.bottom_root
												if next_node:
																		UpperCAmelCase    =				previous_node

																		# Search for new min_node above min_node
																		UpperCAmelCase    =				next_node
																		while i:
																								if i.val < self.min_node.val:
																														UpperCAmelCase    =				i
																								UpperCAmelCase    =				i.parent
        # Merge heaps
												self.merge_heaps(lowercase_      )

												return min_value






						def 			UpperCAmelCase__  (      self				:Union[str, Any]      )       ->    List[Any]:
												UpperCAmelCase    =				self.bottom_root
												while top_root.parent:
																		UpperCAmelCase    =				top_root.parent
												# preorder
												UpperCAmelCase    =				[]
												self.__traversal(lowercase_     ,						lowercase_      )
												return heap_pre_order






						def 			UpperCAmelCase__  (      self				:str     ,						lowercase_				:int     ,						lowercase_				:List[Any]     ,						lowercase_				:Any=0      )       ->    Optional[int]:
												if curr_node:
																		preorder.append((curr_node.val, level)      )
																		self.__traversal(curr_node.left     ,						lowercase_     ,						level + 1      )
																		self.__traversal(curr_node.right     ,						lowercase_     ,						level + 1      )
												else:
																		preorder.append(('#', level)      )






						def __str__(      self				:Tuple      )       ->    str:
												if self.is_empty():
																		return ""
												UpperCAmelCase    =				self.pre_order()

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


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

				doctest.testmod()










"""simple docstring"""


def 				_lowerCAmelCase   (     lowercase_	,			lowercase_		):
						UpperCAmelCase    =				1.0
						for i in range(1	,			r + 1		):
												ret *= (n + 1 - i) / i
						return round(lowercase_		)

def 				_lowerCAmelCase   (     lowercase_		):
						return choose(8 + n	,			lowercase_		) + choose(9 + n	,			lowercase_		) - 10

def 				_lowerCAmelCase   (     lowercase_		):
						return sum(non_bouncy_exact(lowercase_		) for i in range(1	,			n + 1		)		)

def 				_lowerCAmelCase   (     lowercase_ = 100		):
						return non_bouncy_upto(lowercase_		)


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





