


'''simple docstring'''







from __future__ import annotations

import math
import random
from typing import Any
class 						UpperCamelCase__       :



     """simple docstring"""






     def __init__(			self ):

            '''simple docstring'''

            _lowerCAmelCase     :				list[Any]       =							[]
            _lowerCAmelCase     :				int       =							0
            _lowerCAmelCase     :				int       =							0







     def a						(			self ):

            '''simple docstring'''

            return self.head == self.tail







     def a						(			self   ,						snake_case__ ):

            '''simple docstring'''

            self.data.append(snake_case__ )
            _lowerCAmelCase     :				Optional[int]       =							self.tail + 1







     def a						(			self ):

            '''simple docstring'''

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







     def a						(			self ):

            '''simple docstring'''

            return self.tail - self.head







     def a						(			self ):

            '''simple docstring'''

            print(self.data )
            print('**************' )
            print(self.data[self.head : self.tail] )
class 						UpperCamelCase__       :



     """simple docstring"""






     def __init__(			self   ,						snake_case__ ):

            '''simple docstring'''

            _lowerCAmelCase     :				Optional[int]       =							data
            _lowerCAmelCase     :				MyNode | None       =							None
            _lowerCAmelCase     :				MyNode | None       =							None
            _lowerCAmelCase     :				int       =							1







     def a						(			self ):

            '''simple docstring'''

            return self.data







     def a						(			self ):

            '''simple docstring'''

            return self.left







     def a						(			self ):

            '''simple docstring'''

            return self.right







     def a						(			self ):

            '''simple docstring'''

            return self.height







     def a						(			self   ,						snake_case__ ):

            '''simple docstring'''

            _lowerCAmelCase     :				List[str]       =							data







     def a						(			self   ,						snake_case__ ):

            '''simple docstring'''

            _lowerCAmelCase     :				Dict       =							node







     def a						(			self   ,						snake_case__ ):

            '''simple docstring'''

            _lowerCAmelCase     :				Union[str, Any]       =							node







     def a						(			self   ,						snake_case__ ):

            '''simple docstring'''

            _lowerCAmelCase     :				Dict       =							height






def       lowercase					(_A       ):







       """simple docstring"""







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






def       lowercase					(_A ,    _A       ):







       """simple docstring"""







       if a > b:
              return a
       return b






def       lowercase					(_A       ):







       """simple docstring"""







       print('left rotation node:' ,    node.get_data()       )
       _lowerCAmelCase     :				List[Any]       =							node.get_left()
       assert ret is not None
       node.set_left(ret.get_right()       )
       ret.set_right(_A       )
       _lowerCAmelCase     :				Optional[int]       =							my_max(get_height(node.get_right()       ) ,    get_height(node.get_left()       )       ) + 1
       node.set_height(_A       )
       _lowerCAmelCase     :				Any       =							my_max(get_height(ret.get_right()       ) ,    get_height(ret.get_left()       )       ) + 1
       ret.set_height(_A       )
       return ret






def       lowercase					(_A       ):







       """simple docstring"""







       print('right rotation node:' ,    node.get_data()       )
       _lowerCAmelCase     :				Optional[int]       =							node.get_right()
       assert ret is not None
       node.set_right(ret.get_left()       )
       ret.set_left(_A       )
       _lowerCAmelCase     :				List[Any]       =							my_max(get_height(node.get_right()       ) ,    get_height(node.get_left()       )       ) + 1
       node.set_height(_A       )
       _lowerCAmelCase     :				int       =							my_max(get_height(ret.get_right()       ) ,    get_height(ret.get_left()       )       ) + 1
       ret.set_height(_A       )
       return ret






def       lowercase					(_A       ):







       """simple docstring"""







       _lowerCAmelCase     :				Tuple       =							node.get_left()
       assert left_child is not None
       node.set_left(left_rotation(_A       )       )
       return right_rotation(_A       )






def       lowercase					(_A       ):







       """simple docstring"""







       _lowerCAmelCase     :				Tuple       =							node.get_right()
       assert right_child is not None
       node.set_right(right_rotation(_A       )       )
       return left_rotation(_A       )






def       lowercase					(_A ,    _A       ):







       """simple docstring"""







       if node is None:
              return MyNode(_A       )
       if data < node.get_data():
              node.set_left(insert_node(node.get_left() ,    _A       )       )
              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     :				Dict       =							right_rotation(_A       )
                     else:
                            _lowerCAmelCase     :				Optional[Any]       =							lr_rotation(_A       )
       else:
              node.set_right(insert_node(node.get_right() ,    _A       )       )
              if get_height(node.get_right()       ) - get_height(node.get_left()       ) == 2:
                     _lowerCAmelCase     :				Optional[Any]       =							node.get_right()
                     assert right_child is not None
                     if data < right_child.get_data():
                            _lowerCAmelCase     :				Optional[int]       =							rl_rotation(_A       )
                     else:
                            _lowerCAmelCase     :				str       =							left_rotation(_A       )
       _lowerCAmelCase     :				List[Any]       =							my_max(get_height(node.get_right()       ) ,    get_height(node.get_left()       )       ) + 1
       node.set_height(_A       )
       return node






def       lowercase					(_A       ):







       """simple docstring"""







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






def       lowercase					(_A       ):







       """simple docstring"""







       while True:
              _lowerCAmelCase     :				Tuple       =							root.get_left()
              if left_child is None:
                     break
              _lowerCAmelCase     :				str       =							left_child
       return root.get_data()






def       lowercase					(_A ,    _A       ):







       """simple docstring"""







       _lowerCAmelCase     :				Optional[Any]       =							root.get_left()
       _lowerCAmelCase     :				int       =							root.get_right()
       if root.get_data() == data:
              if left_child is not None and right_child is not None:
                     _lowerCAmelCase     :				List[str]       =							get_left_most(_A       )
                     root.set_data(_A       )
                     root.set_right(del_node(_A ,    _A       )       )
              elif left_child is not None:
                     _lowerCAmelCase     :				Union[str, Any]       =							left_child
              elif right_child is not None:
                     _lowerCAmelCase     :				Any       =							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(_A ,    _A       )       )
       else:  # root.get_data() < data
              if right_child is None:
                     return root
              else:
                     root.set_right(del_node(_A ,    _A       )       )

       if get_height(_A       ) - get_height(_A       ) == 2:
              assert right_child is not None
              if get_height(right_child.get_right()       ) > get_height(right_child.get_left()       ):
                     _lowerCAmelCase     :				Dict       =							left_rotation(_A       )
              else:
                     _lowerCAmelCase     :				Optional[Any]       =							rl_rotation(_A       )
       elif get_height(_A       ) - get_height(_A       ) == -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(_A       )
              else:
                     _lowerCAmelCase     :				str       =							lr_rotation(_A       )
       _lowerCAmelCase     :				Any       =							my_max(get_height(root.get_right()       ) ,    get_height(root.get_left()       )       ) + 1
       root.set_height(_A       )
       return root
class 						UpperCamelCase__       :



     """simple docstring"""






     def __init__(			self ):

            '''simple docstring'''

            _lowerCAmelCase     :				MyNode | None       =							None







     def a						(			self ):

            '''simple docstring'''

            return get_height(self.root )







     def a						(			self   ,						snake_case__ ):

            '''simple docstring'''

            print('insert:' + str(snake_case__ ) )
            _lowerCAmelCase     :				Union[str, Any]       =							insert_node(self.root   ,						snake_case__ )







     def a						(			self   ,						snake_case__ ):

            '''simple docstring'''

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







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

            '''simple docstring'''

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






def       lowercase					():







       """simple docstring"""







       import doctest

       doctest.testmod()


if __name__ == "__main__":
       _test()
       lowerCAmelCase     :  List[Any]											=    AVLtree()
       lowerCAmelCase     :  Any											=    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       lowercase					(_A       ):







       """simple docstring"""







       _lowerCAmelCase     :				Union[str, Any]       =							len(_A       )
       for i in range(length - 1       ):
              _lowerCAmelCase     :				List[Any]       =							i
              for k in range(i + 1 ,    _A       ):
                     if collection[k] < collection[least]:
                            _lowerCAmelCase     :				List[str]       =							k
              if least != i:
                     _lowerCAmelCase      ,  _lowerCAmelCase     :				Union[str, Any]       =							(collection[i], collection[least])
       return collection


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

