






from __future__ import annotations

import math
import random
from typing import Any







class 				UpperCAmelCase_  :




     def __init__(				self		):
          UpperCAmelCase__      :  list[Any]				      =			[]
          UpperCAmelCase__      :  int				      =			0
          UpperCAmelCase__      :  int				      =			0




     def   __UpperCAmelCase  (				self		):
          return self.head == self.tail




     def   __UpperCAmelCase  (				self	,						_lowerCAmelCase		):
          self.data.append(_lowerCAmelCase		)
          UpperCAmelCase__      :  Dict				      =			self.tail + 1




     def   __UpperCAmelCase  (				self		):
          UpperCAmelCase__      :  Optional[int]				      =			self.data[self.head]
          UpperCAmelCase__      :  Optional[Any]				      =			self.head + 1
          return ret




     def   __UpperCAmelCase  (				self		):
          return self.tail - self.head




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







class 				UpperCAmelCase_  :




     def __init__(				self	,						_lowerCAmelCase		):
          UpperCAmelCase__      :  List[Any]				      =			data
          UpperCAmelCase__      :  MyNode | None				      =			None
          UpperCAmelCase__      :  MyNode | None				      =			None
          UpperCAmelCase__      :  int				      =			1




     def   __UpperCAmelCase  (				self		):
          return self.data




     def   __UpperCAmelCase  (				self		):
          return self.left




     def   __UpperCAmelCase  (				self		):
          return self.right




     def   __UpperCAmelCase  (				self		):
          return self.height




     def   __UpperCAmelCase  (				self	,						_lowerCAmelCase		):
          UpperCAmelCase__      :  Any				      =			data




     def   __UpperCAmelCase  (				self	,						_lowerCAmelCase		):
          UpperCAmelCase__      :  List[str]				      =			node




     def   __UpperCAmelCase  (				self	,						_lowerCAmelCase		):
          UpperCAmelCase__      :  List[Any]				      =			node




     def   __UpperCAmelCase  (				self	,						_lowerCAmelCase		):
          UpperCAmelCase__      :  Tuple				      =			height





def  _lowerCamelCase						(						__lowerCamelCase       ) ->			int:

     '''simple docstring'''


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





def  _lowerCamelCase						(						__lowerCamelCase ,							__lowerCamelCase       ) ->			int:

     '''simple docstring'''


     if a > b:
          return a
     return b





def  _lowerCamelCase						(						__lowerCamelCase       ) ->			MyNode:

     '''simple docstring'''
     print("""left rotation node:""" ,							node.get_data()       )
     UpperCAmelCase__      :  Optional[Any]				      =			node.get_left()
     assert ret is not None
     node.set_left(ret.get_right()       )
     ret.set_right(_lowerCamelCase       )
     UpperCAmelCase__      :  str				      =			my_max(get_height(node.get_right()       ) ,							get_height(node.get_left()       )       ) + 1
     node.set_height(_lowerCamelCase       )
     UpperCAmelCase__      :  List[Any]				      =			my_max(get_height(ret.get_right()       ) ,							get_height(ret.get_left()       )       ) + 1
     ret.set_height(_lowerCamelCase       )
     return ret





def  _lowerCamelCase						(						__lowerCamelCase       ) ->			MyNode:

     '''simple docstring'''
     print("""right rotation node:""" ,							node.get_data()       )
     UpperCAmelCase__      :  Optional[Any]				      =			node.get_right()
     assert ret is not None
     node.set_right(ret.get_left()       )
     ret.set_left(_lowerCamelCase       )
     UpperCAmelCase__      :  Tuple				      =			my_max(get_height(node.get_right()       ) ,							get_height(node.get_left()       )       ) + 1
     node.set_height(_lowerCamelCase       )
     UpperCAmelCase__      :  Any				      =			my_max(get_height(ret.get_right()       ) ,							get_height(ret.get_left()       )       ) + 1
     ret.set_height(_lowerCamelCase       )
     return ret





def  _lowerCamelCase						(						__lowerCamelCase       ) ->			MyNode:

     '''simple docstring'''
     UpperCAmelCase__      :  str				      =			node.get_left()
     assert left_child is not None
     node.set_left(left_rotation(_lowerCamelCase       )       )
     return right_rotation(_lowerCamelCase       )





def  _lowerCamelCase						(						__lowerCamelCase       ) ->			MyNode:

     '''simple docstring'''
     UpperCAmelCase__      :  Optional[int]				      =			node.get_right()
     assert right_child is not None
     node.set_right(right_rotation(_lowerCamelCase       )       )
     return left_rotation(_lowerCamelCase       )





def  _lowerCamelCase						(						__lowerCamelCase ,							__lowerCamelCase       ) ->			MyNode | None:

     '''simple docstring'''


     if node is None:
          return MyNode(_lowerCamelCase       )
     if data < node.get_data():
          node.set_left(insert_node(node.get_left() ,							_lowerCamelCase       )       )
          if (
              get_height(node.get_left()       ) - get_height(node.get_right()       ) == 2
          ):  # an unbalance detected
               UpperCAmelCase__      :  Union[str, Any]				      =			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
                    UpperCAmelCase__      :  Any				      =			right_rotation(_lowerCamelCase       )
               else:
                    UpperCAmelCase__      :  Tuple				      =			lr_rotation(_lowerCamelCase       )
     else:
          node.set_right(insert_node(node.get_right() ,							_lowerCamelCase       )       )
          if get_height(node.get_right()       ) - get_height(node.get_left()       ) == 2:
               UpperCAmelCase__      :  Optional[int]				      =			node.get_right()
               assert right_child is not None
               if data < right_child.get_data():
                    UpperCAmelCase__      :  Optional[int]				      =			rl_rotation(_lowerCamelCase       )
               else:
                    UpperCAmelCase__      :  Tuple				      =			left_rotation(_lowerCamelCase       )
     UpperCAmelCase__      :  Optional[Any]				      =			my_max(get_height(node.get_right()       ) ,							get_height(node.get_left()       )       ) + 1
     node.set_height(_lowerCamelCase       )
     return node





def  _lowerCamelCase						(						__lowerCamelCase       ) ->			Any:

     '''simple docstring'''


     while True:
          UpperCAmelCase__      :  Dict				      =			root.get_right()
          if right_child is None:
               break
          UpperCAmelCase__      :  List[Any]				      =			right_child
     return root.get_data()





def  _lowerCamelCase						(						__lowerCamelCase       ) ->			Any:

     '''simple docstring'''


     while True:
          UpperCAmelCase__      :  Optional[Any]				      =			root.get_left()
          if left_child is None:
               break
          UpperCAmelCase__      :  int				      =			left_child
     return root.get_data()





def  _lowerCamelCase						(						__lowerCamelCase ,							__lowerCamelCase       ) ->			MyNode | None:

     '''simple docstring'''
     UpperCAmelCase__      :  int				      =			root.get_left()
     UpperCAmelCase__      :  int				      =			root.get_right()
     if root.get_data() == data:
          if left_child is not None and right_child is not None:
               UpperCAmelCase__      :  Tuple				      =			get_left_most(_lowerCamelCase       )
               root.set_data(_lowerCamelCase       )
               root.set_right(del_node(_lowerCamelCase ,							_lowerCamelCase       )       )
          elif left_child is not None:
               UpperCAmelCase__      :  Optional[int]				      =			left_child
          elif right_child is not None:
               UpperCAmelCase__      :  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(_lowerCamelCase ,							_lowerCamelCase       )       )
     else:  # root.get_data() < data
          if right_child is None:
               return root
          else:
               root.set_right(del_node(_lowerCamelCase ,							_lowerCamelCase       )       )

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







class 				UpperCAmelCase_  :




     def __init__(				self		):
          UpperCAmelCase__      :  MyNode | None				      =			None




     def   __UpperCAmelCase  (				self		):
          return get_height(self.root		)




     def   __UpperCAmelCase  (				self	,						_lowerCAmelCase		):
          print("""insert:""" + str(_lowerCAmelCase		)		)
          UpperCAmelCase__      :  Optional[Any]				      =			insert_node(self.root	,						_lowerCAmelCase		)




     def   __UpperCAmelCase  (				self	,						_lowerCAmelCase		):
          print("""delete:""" + str(_lowerCAmelCase		)		)
          if self.root is None:
               print("""Tree is empty!"""		)
               return
          UpperCAmelCase__      :  str				      =			del_node(self.root	,						_lowerCAmelCase		)




     def __str__(				self	,						):  # a level traversale, gives a more intuitive look on the tree
          UpperCAmelCase__      :  List[Any]				      =			""""""
          UpperCAmelCase__      :  int				      =			MyQueue()
          q.push(self.root		)
          UpperCAmelCase__      :  int				      =			self.get_height()
          if layer == 0:
               return output
          UpperCAmelCase__      :  Any				      =			0
          while not q.is_empty():
               UpperCAmelCase__      :  Optional[int]				      =			q.pop()
               UpperCAmelCase__      :  Optional[int]				      =			""" """ * int(math.pow(2	,						layer - 1		)		)
               output += space
               if node is None:
                    output += "*"
                    q.push(_lowerCAmelCase		)
                    q.push(_lowerCAmelCase		)
               else:
                    output += str(node.get_data()		)
                    q.push(node.get_left()		)
                    q.push(node.get_right()		)
               output += space
               UpperCAmelCase__      :  Tuple				      =			cnt + 1
               for i in range(100		):
                    if cnt == math.pow(2	,						_lowerCAmelCase		) - 1:
                         UpperCAmelCase__      :  Tuple				      =			layer - 1
                         if layer == 0:
                              output += "\n*************************************"
                              return output
                         output += "\n"
                         break
          output += "\n*************************************"
          return output





def  _lowerCamelCase						(						) ->			None:

     '''simple docstring'''
     import doctest

     doctest.testmod()


if __name__ == "__main__":
      _test()
      SCREAMING_SNAKE_CASE__		:							Optional[int] 				=				AVLtree()
      SCREAMING_SNAKE_CASE__		:							Optional[int] 				=				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))













'''simple docstring'''






def 					_a						(       _lowerCamelCase = 100 ) ->				int:



			"""simple docstring"""


			__snake_case					:      Any							      =     n * (n + 1) * (2 * n + 1) / 6
			__snake_case					:      List[Any]							      =     (n * (n + 1) / 2) ** 2
			return int(square_of_sum - sum_of_squares )


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


