'''simple docstring'''






from typing import Any





class     A__							:





   """simple docstring"""





   def __init__( self     :		int						,     lowerCAmelCase__     :		Any			)       ->    Optional[Any]:







      """simple docstring"""




      _UpperCAmelCase							:	Optional[Any]							=   data
      _UpperCAmelCase							:	int							=   None




   def __repr__( self     :		Any			)       ->    Tuple:







      """simple docstring"""




      return F"""Node({self.data})"""





class     A__							:





   """simple docstring"""





   def __init__( self     :		Dict			)       ->    List[Any]:







      """simple docstring"""




      _UpperCAmelCase							:	int							=   None




   def __iter__( self     :		Optional[int]			)       ->    Optional[int]:







      """simple docstring"""




      _UpperCAmelCase							:	Union[str, Any]							=   self.head
      while node:
         yield node.data
         _UpperCAmelCase							:	Union[str, Any]							=   node.next




   def __len__( self     :		Tuple			)       ->    Union[str, Any]:







      """simple docstring"""




      return sum(1 for _ in self			)




   def __repr__( self     :		Any			)       ->    Tuple:







      """simple docstring"""




      return "->".join([str(lowerCAmelCase__			) for item in self]			)




   def __getitem__( self     :		List[str]						,     lowerCAmelCase__     :		int			)       ->    List[Any]:







      """simple docstring"""




      if not 0 <= index < len(self			):
         raise ValueError("list index out of range."			)
      for i, node in enumerate(self			):
         if i == index:
            return node
      return None




   def __setitem__( self     :		str						,     lowerCAmelCase__     :		int						,     lowerCAmelCase__     :		Any			)       ->    List[Any]:







      """simple docstring"""




      if not 0 <= index < len(self			):
         raise ValueError("list index out of range."			)
      _UpperCAmelCase							:	Tuple							=   self.head
      for _ in range(lowerCAmelCase__			):
         _UpperCAmelCase							:	Union[str, Any]							=   current.next
      _UpperCAmelCase							:	Tuple							=   data




   def 			_lowerCAmelCase		( self     :		Union[str, Any]						,     lowerCAmelCase__     :		Any			)       ->    Any:







      """simple docstring"""




      self.insert_nth(len(self			)						,     lowerCAmelCase__			)




   def 			_lowerCAmelCase		( self     :		Any						,     lowerCAmelCase__     :		Any			)       ->    int:







      """simple docstring"""




      self.insert_nth(0						,     lowerCAmelCase__			)




   def 			_lowerCAmelCase		( self     :		Dict						,     lowerCAmelCase__     :		int						,     lowerCAmelCase__     :		Any			)       ->    Optional[int]:







      """simple docstring"""




      if not 0 <= index <= len(self			):
         raise IndexError("list index out of range"			)
      _UpperCAmelCase							:	List[str]							=   Node(lowerCAmelCase__			)
      if self.head is None:
         _UpperCAmelCase							:	Optional[Any]							=   new_node
      elif index == 0:
         _UpperCAmelCase							:	Tuple							=   self.head  # link new_node to head
         _UpperCAmelCase							:	str							=   new_node
      else:
         _UpperCAmelCase							:	str							=   self.head
         for _ in range(index - 1			):
            _UpperCAmelCase							:	Union[str, Any]							=   temp.next
         _UpperCAmelCase							:	List[Any]							=   temp.next
         _UpperCAmelCase							:	Dict							=   new_node




   def 			_lowerCAmelCase		( self     :		int			)       ->    Union[str, Any]:  # print every node data







      """simple docstring"""




      print(self			)




   def 			_lowerCAmelCase		( self     :		Optional[int]			)       ->    Optional[int]:







      """simple docstring"""




      return self.delete_nth(0			)




   def 			_lowerCAmelCase		( self     :		Any			)       ->    Optional[int]:  # delete from tail







      """simple docstring"""




      return self.delete_nth(len(self			) - 1			)




   def 			_lowerCAmelCase		( self     :		str						,     lowerCAmelCase__     :		int = 0			)       ->    Tuple:







      """simple docstring"""




      if not 0 <= index <= len(self			) - 1:  # test if index is valid
         raise IndexError("List index out of range."			)
      _UpperCAmelCase							:	Dict							=   self.head  # default first node
      if index == 0:
         _UpperCAmelCase							:	Union[str, Any]							=   self.head.next
      else:
         _UpperCAmelCase							:	int							=   self.head
         for _ in range(index - 1			):
            _UpperCAmelCase							:	List[str]							=   temp.next
         _UpperCAmelCase							:	int							=   temp.next
         _UpperCAmelCase							:	Optional[Any]							=   temp.next.next
      return delete_node.data




   def 			_lowerCAmelCase		( self     :		Tuple			)       ->    int:







      """simple docstring"""




      return self.head is None




   def 			_lowerCAmelCase		( self     :		str			)       ->    Any:







      """simple docstring"""




      _UpperCAmelCase							:	List[str]							=   None
      _UpperCAmelCase							:	Tuple							=   self.head

      while current:
         # Store the current node's next node.
         _UpperCAmelCase							:	Optional[int]							=   current.next
         # Make the current node's next point backwards
         _UpperCAmelCase							:	Optional[Any]							=   prev
         # Make the previous node be the current node
         _UpperCAmelCase							:	List[Any]							=   current
         # Make the current node the next node (to progress iteration)
         _UpperCAmelCase							:	Tuple							=   next_node
      # Return prev in order to put the head at the end
      _UpperCAmelCase							:	Any							=   prev






def    __UpperCAmelCase			(  ):
   _UpperCAmelCase							:	Union[str, Any]							=   LinkedList()
   assert linked_list.is_empty() is True
   assert str(_lowerCamelCase							) == ""

   try:
      linked_list.delete_head()
      raise AssertionError  # This should not happen.
   except IndexError:
      assert True  # This should happen.

   try:
      linked_list.delete_tail()
      raise AssertionError  # This should not happen.
   except IndexError:
      assert True  # This should happen.

   for i in range(10							):
      assert len(_lowerCamelCase							) == i
      linked_list.insert_nth(_lowerCamelCase,					i + 1							)
   assert str(_lowerCamelCase							) == "->".join(str(_lowerCamelCase							) for i in range(1,					11							)							)

   linked_list.insert_head(0							)
   linked_list.insert_tail(11							)
   assert str(_lowerCamelCase							) == "->".join(str(_lowerCamelCase							) for i in range(0,					12							)							)

   assert linked_list.delete_head() == 0
   assert linked_list.delete_nth(9							) == 10
   assert linked_list.delete_tail() == 11
   assert len(_lowerCamelCase							) == 9
   assert str(_lowerCamelCase							) == "->".join(str(_lowerCamelCase							) for i in range(1,					10							)							)

   assert all(linked_list[i] == i + 1 for i in range(0,					9							)							) is True

   for i in range(0,					9							):
      _UpperCAmelCase							:	List[Any]							=   -i
   assert all(linked_list[i] == -i for i in range(0,					9							)							) is True

   linked_list.reverse()
   assert str(_lowerCamelCase							) == "->".join(str(_lowerCamelCase							) for i in range(-8,					1							)							)






def    __UpperCAmelCase			(  ):
   _UpperCAmelCase							:	str							=   [
       -9,
       100,
       Node(77_345_112							),
       """dlrow olleH""",
       7,
       5_555,
       0,
       -192.55_555,
       """Hello, world!""",
       77.9,
       Node(10							),
       None,
       None,
       12.20,
   ]
   _UpperCAmelCase							:	Any							=   LinkedList()

   for i in test_input:
      linked_list.insert_tail(_lowerCamelCase							)

   # Check if it's empty or not
   assert linked_list.is_empty() is False
   assert (
       str(_lowerCamelCase							) == "-9->100->Node(77345112)->dlrow olleH->7->5555->0->"
       "-192.55555->Hello, world!->77.9->Node(10)->None->None->12.2"
   )

   # Delete the head
   _UpperCAmelCase							:	Optional[Any]							=   linked_list.delete_head()
   assert result == -9
   assert (
       str(_lowerCamelCase							) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
       "Hello, world!->77.9->Node(10)->None->None->12.2"
   )

   # Delete the tail
   _UpperCAmelCase							:	Tuple							=   linked_list.delete_tail()
   assert result == 12.2
   assert (
       str(_lowerCamelCase							) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
       "Hello, world!->77.9->Node(10)->None->None"
   )

   # Delete a node in specific location in linked list
   _UpperCAmelCase							:	Any							=   linked_list.delete_nth(10							)
   assert result is None
   assert (
       str(_lowerCamelCase							) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
       "Hello, world!->77.9->Node(10)->None"
   )

   # Add a Node instance to its head
   linked_list.insert_head(Node("Hello again, world!"							)							)
   assert (
       str(_lowerCamelCase							)
       == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
       "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None"
   )

   # Add None to its tail
   linked_list.insert_tail(_lowerCamelCase							)
   assert (
       str(_lowerCamelCase							)
       == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
       "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None->None"
   )

   # Reverse the linked list
   linked_list.reverse()
   assert (
       str(_lowerCamelCase							)
       == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
       "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
   )






def    __UpperCAmelCase			(  ):
   from doctest import testmod

   testmod()

   _UpperCAmelCase							:	List[Any]							=   LinkedList()
   linked_list.insert_head(input("Inserting 1st at head "							).strip()							)
   linked_list.insert_head(input("Inserting 2nd at head "							).strip()							)
   print("\nPrint list:"							)
   linked_list.print_list()
   linked_list.insert_tail(input("\nInserting 1st at tail "							).strip()							)
   linked_list.insert_tail(input("Inserting 2nd at tail "							).strip()							)
   print("\nPrint list:"							)
   linked_list.print_list()
   print("\nDelete head"							)
   linked_list.delete_head()
   print("Delete tail"							)
   linked_list.delete_tail()
   print("\nPrint list:"							)
   linked_list.print_list()
   print("\nReverse linked list"							)
   linked_list.reverse()
   print("\nPrint list:"							)
   linked_list.print_list()
   print("\nString representation of linked list:"							)
   print(_lowerCamelCase							)
   print("\nReading/changing Node data using indexing:"							)
   print(f"""Element at Position 1: {linked_list[1]}"""							)
   _UpperCAmelCase							:	Dict							=   input("Enter New Value: "							).strip()
   print("New list:"							)
   print(_lowerCamelCase							)
   print(f"""length of linked_list is : {len(_lowerCamelCase							)}"""							)


if __name__ == "__main__":
     main()




'''simple docstring'''




def 				lowerCAmelCase_   (	_lowerCamelCase:   list					):
		if any(not isinstance(_lowerCamelCase       ,      _lowerCamelCase					) or x < 0 for x in sequence					):
				raise TypeError("""Sequence must be list of non-negative integers"""					)
		for _ in range(len(_lowerCamelCase					)					):
				for i, (rod_upper, rod_lower) in enumerate(zip(_lowerCamelCase       ,      sequence[1:]					)					):
						if rod_upper > rod_lower:
								sequence[i] -= rod_upper - rod_lower
								sequence[i + 1] += rod_upper - rod_lower
		return sequence


if __name__ == "__main__":
						assert bead_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
						assert bead_sort([7, 9, 4, 3, 5]) == [3, 4, 5, 7, 9]