



from __future__ import annotations

import math
import random
from typing import Any



class 						UpperCAmelCase_					:







							def __init__(     self):

														'''simple docstring'''

														_lowerCAmelCase  :							List[Any]				     =					[]
														_lowerCAmelCase  :							str				     =					0
														_lowerCAmelCase  :							List[Any]				     =					0







							def      snake_case__   (     self):

														'''simple docstring'''

														return self.head == self.tail







							def      snake_case__   (     self,    __a):

														'''simple docstring'''

														self.data.append(__a)
														_lowerCAmelCase  :							Union[str, Any]				     =					self.tail + 1







							def      snake_case__   (     self):

														'''simple docstring'''

														_lowerCAmelCase  :							Tuple				     =					self.data[self.head]
														_lowerCAmelCase  :							Dict				     =					self.head + 1
														return ret







							def      snake_case__   (     self):

														'''simple docstring'''

														return self.tail - self.head







							def      snake_case__   (     self):

														'''simple docstring'''

														print(self.data)
														print("**************")
														print(self.data[self.head : self.tail])



class 						UpperCAmelCase_					:







							def __init__(     self,    __a):

														'''simple docstring'''

														_lowerCAmelCase  :							List[str]				     =					data
														_lowerCAmelCase  :							Union[str, Any]				     =					None
														_lowerCAmelCase  :							Union[str, Any]				     =					None
														_lowerCAmelCase  :							Tuple				     =					1







							def      snake_case__   (     self):

														'''simple docstring'''

														return self.data







							def      snake_case__   (     self):

														'''simple docstring'''

														return self.left







							def      snake_case__   (     self):

														'''simple docstring'''

														return self.right







							def      snake_case__   (     self):

														'''simple docstring'''

														return self.height







							def      snake_case__   (     self,    __a):

														'''simple docstring'''

														_lowerCAmelCase  :							List[str]				     =					data







							def      snake_case__   (     self,    __a):

														'''simple docstring'''

														_lowerCAmelCase  :							List[str]				     =					node







							def      snake_case__   (     self,    __a):

														'''simple docstring'''

														_lowerCAmelCase  :							Optional[Any]				     =					node







							def      snake_case__   (     self,    __a):

														'''simple docstring'''

														_lowerCAmelCase  :							str				     =					height






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




							if node is None:
														return 0
							return node.get_height()






def        A       (      _lowerCamelCase       ,				_lowerCamelCase						):





							'''simple docstring'''




							if a > b:
														return a
							return b






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




							print("left rotation node:"       ,				node.get_data()						)
							_lowerCAmelCase  :							List[str]				     =					node.get_left()
							assert ret is not None
							node.set_left(ret.get_right()						)
							ret.set_right(_snake_case						)
							_lowerCAmelCase  :							Union[str, Any]				     =					my_max(get_height(node.get_right()						)       ,				get_height(node.get_left()						)						) + 1
							node.set_height(_snake_case						)
							_lowerCAmelCase  :							List[Any]				     =					my_max(get_height(ret.get_right()						)       ,				get_height(ret.get_left()						)						) + 1
							ret.set_height(_snake_case						)
							return ret






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




							print("right rotation node:"       ,				node.get_data()						)
							_lowerCAmelCase  :							Optional[Any]				     =					node.get_right()
							assert ret is not None
							node.set_right(ret.get_left()						)
							ret.set_left(_snake_case						)
							_lowerCAmelCase  :							str				     =					my_max(get_height(node.get_right()						)       ,				get_height(node.get_left()						)						) + 1
							node.set_height(_snake_case						)
							_lowerCAmelCase  :							Union[str, Any]				     =					my_max(get_height(ret.get_right()						)       ,				get_height(ret.get_left()						)						) + 1
							ret.set_height(_snake_case						)
							return ret






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




							_lowerCAmelCase  :							Optional[Any]				     =					node.get_left()
							assert left_child is not None
							node.set_left(left_rotation(_snake_case						)						)
							return right_rotation(_snake_case						)






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




							_lowerCAmelCase  :							List[Any]				     =					node.get_right()
							assert right_child is not None
							node.set_right(right_rotation(_snake_case						)						)
							return left_rotation(_snake_case						)






def        A       (      _lowerCamelCase       ,				_lowerCamelCase						):





							'''simple docstring'''




							if node is None:
														return MyNode(_snake_case						)
							if data < node.get_data():
														node.set_left(insert_node(node.get_left()       ,				_snake_case						)						)
														if (
														    get_height(node.get_left()						) - get_height(node.get_right()						) == 2
														):  # an unbalance detected
																					_lowerCAmelCase  :							Tuple				     =					node.get_left()
																					assert left_child is not None
																					if (
																					    data < left_child.get_data()
																					):  # new node is the left child of the left child
																												_lowerCAmelCase  :							List[Any]				     =					right_rotation(_snake_case						)
																					else:
																												_lowerCAmelCase  :							Tuple				     =					lr_rotation(_snake_case						)
							else:
														node.set_right(insert_node(node.get_right()       ,				_snake_case						)						)
														if get_height(node.get_right()						) - get_height(node.get_left()						) == 2:
																					_lowerCAmelCase  :							List[str]				     =					node.get_right()
																					assert right_child is not None
																					if data < right_child.get_data():
																												_lowerCAmelCase  :							Union[str, Any]				     =					rl_rotation(_snake_case						)
																					else:
																												_lowerCAmelCase  :							List[str]				     =					left_rotation(_snake_case						)
							_lowerCAmelCase  :							Any				     =					my_max(get_height(node.get_right()						)       ,				get_height(node.get_left()						)						) + 1
							node.set_height(_snake_case						)
							return node






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




							while True:
														_lowerCAmelCase  :							str				     =					root.get_right()
														if right_child is None:
																					break
														_lowerCAmelCase  :							int				     =					right_child
							return root.get_data()






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




							while True:
														_lowerCAmelCase  :							Union[str, Any]				     =					root.get_left()
														if left_child is None:
																					break
														_lowerCAmelCase  :							str				     =					left_child
							return root.get_data()






def        A       (      _lowerCamelCase       ,				_lowerCamelCase						):





							'''simple docstring'''




							_lowerCAmelCase  :							Dict				     =					root.get_left()
							_lowerCAmelCase  :							Any				     =					root.get_right()
							if root.get_data() == data:
														if left_child is not None and right_child is not None:
																					_lowerCAmelCase  :							int				     =					get_left_most(_snake_case						)
																					root.set_data(_snake_case						)
																					root.set_right(del_node(_snake_case       ,				_snake_case						)						)
														elif left_child is not None:
																					_lowerCAmelCase  :							Dict				     =					left_child
														elif right_child is not None:
																					_lowerCAmelCase  :							str				     =					right_child
														else:
																					return None
							elif root.get_data() > data:
														if left_child is None:
																					print("No such data"						)
																					return root
														else:
																					root.set_left(del_node(_snake_case       ,				_snake_case						)						)
							else:  # root.get_data() < data
														if right_child is None:
																					return root
														else:
																					root.set_right(del_node(_snake_case       ,				_snake_case						)						)

							if get_height(_snake_case						) - get_height(_snake_case						) == 2:
														assert right_child is not None
														if get_height(right_child.get_right()						) > get_height(right_child.get_left()						):
																					_lowerCAmelCase  :							Dict				     =					left_rotation(_snake_case						)
														else:
																					_lowerCAmelCase  :							str				     =					rl_rotation(_snake_case						)
							elif get_height(_snake_case						) - get_height(_snake_case						) == -2:
														assert left_child is not None
														if get_height(left_child.get_left()						) > get_height(left_child.get_right()						):
																					_lowerCAmelCase  :							List[Any]				     =					right_rotation(_snake_case						)
														else:
																					_lowerCAmelCase  :							Dict				     =					lr_rotation(_snake_case						)
							_lowerCAmelCase  :							str				     =					my_max(get_height(root.get_right()						)       ,				get_height(root.get_left()						)						) + 1
							root.set_height(_snake_case						)
							return root



class 						UpperCAmelCase_					:







							def __init__(     self):

														'''simple docstring'''

														_lowerCAmelCase  :							Any				     =					None







							def      snake_case__   (     self):

														'''simple docstring'''

														return get_height(self.root)







							def      snake_case__   (     self,    __a):

														'''simple docstring'''

														print("insert:" + str(__a))
														_lowerCAmelCase  :							str				     =					insert_node(self.root,    __a)







							def      snake_case__   (     self,    __a):

														'''simple docstring'''

														print("delete:" + str(__a))
														if self.root is None:
																					print("Tree is empty!")
																					return
														_lowerCAmelCase  :							Union[str, Any]				     =					del_node(self.root,    __a)







							def __str__(     self,    ):  # a level traversale, gives a more intuitive look on the tree

														'''simple docstring'''

														_lowerCAmelCase  :							List[Any]				     =					""
														_lowerCAmelCase  :							List[Any]				     =					MyQueue()
														q.push(self.root)
														_lowerCAmelCase  :							Union[str, Any]				     =					self.get_height()
														if layer == 0:
																					return output
														_lowerCAmelCase  :							Dict				     =					0
														while not q.is_empty():
																					_lowerCAmelCase  :							List[str]				     =					q.pop()
																					_lowerCAmelCase  :							int				     =					" " * int(math.pow(2,    layer - 1))
																					output += space
																					if node is None:
																												output += "*"
																												q.push(__a)
																												q.push(__a)
																					else:
																												output += str(node.get_data())
																												q.push(node.get_left())
																												q.push(node.get_right())
																					output += space
																					_lowerCAmelCase  :							int				     =					cnt + 1
																					for i in range(100):
																												if cnt == math.pow(2,    __a) - 1:
																																			_lowerCAmelCase  :							Any				     =					layer - 1
																																			if layer == 0:
																																										output += "\n*************************************"
																																										return output
																																			output += "\n"
																																			break
														output += "\n*************************************"
														return output






def        A       (      ):





							'''simple docstring'''




							import doctest

							doctest.testmod()


if __name__ == "__main__":
						_test()
						_snake_case	=						AVLtree()
						_snake_case	=						list(range(10))
						random.shuffle(lst)
						for i in lst:
												t.insert(i)
												print(str(t))
						random.shuffle(lst)
						for i in lst:
												t.del_node(i)
												print(str(t))





def        A       (      _lowerCamelCase						):





							'''simple docstring'''




							_lowerCAmelCase  :							int				     =					len(_lowerCamelCase						)
							for i in range(1       ,				_lowerCamelCase						):
														_lowerCAmelCase  :							List[Any]				     =					collection[i]
														_lowerCAmelCase  :							str				     =					0
														_lowerCAmelCase  :							Union[str, Any]				     =					i - 1

														while low <= high:
																					_lowerCAmelCase  :							List[str]				     =					(low + high) // 2
																					if val < collection[mid]:
																												_lowerCAmelCase  :							Optional[int]				     =					mid - 1
																					else:
																												_lowerCAmelCase  :							List[str]				     =					mid + 1
														for j in range(_lowerCamelCase       ,				_lowerCamelCase       ,				-1						):
																					_lowerCAmelCase  :							int				     =					collection[j - 1]
														_lowerCAmelCase  :							Optional[int]				     =					val
							return collection


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