





"""simple docstring"""



class 						__snake_case   :





 """simple docstring"""


 def __init__(       self   ,		__lowerCamelCase   ,		__lowerCamelCase=None   ,		__lowerCamelCase=None    ):



     '''simple docstring'''




     __A       :		List[str]							=	data
     __A       :		Tuple							=	previous
     __A       :		int							=	next_node

 def __str__(       self    ):



     '''simple docstring'''




     return F"""{self.data}"""

 def    UpperCamelCase__(       self    ):



     '''simple docstring'''




     return self.data

 def    UpperCamelCase__(       self    ):



     '''simple docstring'''




     return self.next







 def    UpperCamelCase__(       self    ):



     '''simple docstring'''




     return self.previous






class 						__snake_case   :





 """simple docstring"""


 def __init__(       self   ,		__lowerCamelCase    ):



     '''simple docstring'''




     __A       :		List[Any]							=	head

 def __iter__(       self    ):



     '''simple docstring'''




     return self







 def    UpperCamelCase__(       self    ):



     '''simple docstring'''




     if not self.current:
         raise StopIteration
     else:
         __A       :		Tuple							=	self.current.get_data()
         __A       :		List[str]							=	self.current.get_next()
         return value






class 						__snake_case   :





 """simple docstring"""


 def __init__(       self    ):



     '''simple docstring'''




     __A       :		Optional[int]							=	None  # First node in list
     __A       :		Union[str, Any]							=	None  # Last node in list

 def __str__(       self    ):



     '''simple docstring'''




     __A       :		Any							=	self.head
     __A       :		List[str]							=	[]
     while current is not None:
         nodes.append(current.get_data()    )
         __A       :		Union[str, Any]							=	current.get_next()
     return " ".join(str(__lowerCamelCase    ) for node in nodes    )

 def __contains__(       self   ,		__lowerCamelCase    ):



     '''simple docstring'''




     __A       :		List[str]							=	self.head
     while current:
         if current.get_data() == value:
             return True
         __A       :		Optional[int]							=	current.get_next()
     return False

 def __iter__(       self    ):



     '''simple docstring'''




     return LinkedListIterator(self.head    )

 def    UpperCamelCase__(       self    ):



     '''simple docstring'''




     if self.head:
         return self.head.get_data()
     return None

 def    UpperCamelCase__(       self    ):



     '''simple docstring'''




     if self.tail:
         return self.tail.get_data()
     return None

 def    UpperCamelCase__(       self   ,		__lowerCamelCase    ):



     '''simple docstring'''




     if self.head is None:
         __A       :		Union[str, Any]							=	node
         __A       :		str							=	node
     else:
         self.insert_before_node(self.head   ,		__lowerCamelCase    )

 def    UpperCamelCase__(       self   ,		__lowerCamelCase    ):



     '''simple docstring'''




     if self.head is None:
         self.set_head(__lowerCamelCase    )
     else:
         self.insert_after_node(self.tail   ,		__lowerCamelCase    )

 def    UpperCamelCase__(       self   ,		__lowerCamelCase    ):



     '''simple docstring'''




     __A       :		List[str]							=	Node(__lowerCamelCase    )
     if self.head is None:
         self.set_head(__lowerCamelCase    )
     else:
         self.set_tail(__lowerCamelCase    )

 def    UpperCamelCase__(       self   ,		__lowerCamelCase   ,		__lowerCamelCase    ):



     '''simple docstring'''




     __A       :		Optional[int]							=	node
     __A       :		Optional[Any]							=	node.previous

     if node.get_previous() is None:
         __A       :		Dict							=	node_to_insert
     else:
         __A       :		List[Any]							=	node_to_insert

     __A       :		Optional[Any]							=	node_to_insert

 def    UpperCamelCase__(       self   ,		__lowerCamelCase   ,		__lowerCamelCase    ):



     '''simple docstring'''




     __A       :		Tuple							=	node
     __A       :		int							=	node.next

     if node.get_next() is None:
         __A       :		List[Any]							=	node_to_insert
     else:
         __A       :		List[str]							=	node_to_insert

     __A       :		List[Any]							=	node_to_insert

 def    UpperCamelCase__(       self   ,		__lowerCamelCase   ,		__lowerCamelCase    ):



     '''simple docstring'''




     __A       :		Union[str, Any]							=	1
     __A       :		str							=	Node(__lowerCamelCase    )
     __A       :		Any							=	self.head
     while node:
         if current_position == position:
             self.insert_before_node(__lowerCamelCase   ,		__lowerCamelCase    )
             return
         current_position += 1
         __A       :		int							=	node.next
     self.insert_after_node(self.tail   ,		__lowerCamelCase    )

 def    UpperCamelCase__(       self   ,		__lowerCamelCase    ):



     '''simple docstring'''




     __A       :		Dict							=	self.head
     while node:
         if node.get_data() == item:
             return node
         __A       :		str							=	node.get_next()
     raise Exception('''Node not found'''    )

 def    UpperCamelCase__(       self   ,		__lowerCamelCase    ):



     '''simple docstring'''




     if (node := self.get_node(__lowerCamelCase    )) is not None:
         if node == self.head:
             __A       :		int							=	self.head.get_next()

         if node == self.tail:
             __A       :		List[Any]							=	self.tail.get_previous()

         self.remove_node_pointers(__lowerCamelCase    )

 @staticmethod
 def    UpperCamelCase__(       __lowerCamelCase    ):



     '''simple docstring'''




     if node.get_next():
         __A       :		Dict							=	node.previous

     if node.get_previous():
         __A       :		Tuple							=	node.next

     __A       :		List[Any]							=	None
     __A       :		List[Any]							=	None







 def    UpperCamelCase__(       self    ):



     '''simple docstring'''




     return self.head is None







def 						__lowercase	(  )  ->None:



    '''simple docstring'''









if __name__ == "__main__":
       import doctest

       doctest.testmod()











"""simple docstring"""



def 						__lowercase	(  snake_case_    :    list		)  ->list:



    '''simple docstring'''







    for i in range(len(snake_case_		) - 1							,0							,-1		):
        __A       :		Union[str, Any]							=	False

        for j in range(snake_case_							,0							,-1		):
            if unsorted[j] < unsorted[j - 1]:
                __A					,			__A       :		Union[str, Any]							=	unsorted[j - 1], unsorted[j]
                __A       :		Optional[int]							=	True

        for j in range(snake_case_		):
            if unsorted[j] > unsorted[j + 1]:
                __A					,			__A       :		Optional[Any]							=	unsorted[j + 1], unsorted[j]
                __A       :		Union[str, Any]							=	True

        if not swapped:
            break
    return unsorted


if __name__ == "__main__":
       import doctest

       doctest.testmod()
       a_					=     input("""Enter numbers separated by a comma:\n""").strip()
       a_					=     [int(item) for item in user_input.split(""",""")]
       print(f'''{cocktail_shaker_sort(unsorted) = }''')




