






'''simple docstring'''

class      A     :






 """simple docstring"""





 def __init__(				self      ,  __lowerCAmelCase      ,  __lowerCAmelCase			):
       UpperCamelCase_					: Tuple            =				name
       UpperCamelCase_					: Union[str, Any]            =				val
 def __str__(				self			):
       return F"{self.__class__.__name__}({self.name}, {self.val})"





 def __lt__(				self      ,  __lowerCAmelCase			):
       return self.val < other.val






class      A     :






 """simple docstring"""





 def __init__(				self      ,  __lowerCAmelCase			):
       UpperCamelCase_					: int            =				{}
       UpperCamelCase_					: Tuple            =				{}
       UpperCamelCase_					: str            =				self.build_heap(__lowerCAmelCase			)
 def __getitem__(				self      ,  __lowerCAmelCase			):
       return self.get_value(__lowerCAmelCase			)
 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase			):
       return (idx - 1) // 2
 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase			):
       return idx * 2 + 1
 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase			):
       return idx * 2 + 2
 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase			):
       return self.heap_dict[key]
 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase			):
       UpperCamelCase_					: Optional[int]            =				len(__lowerCAmelCase			) - 1
       UpperCamelCase_					: List[str]            =				self.get_parent_idx(__lowerCAmelCase			)

       for idx, i in enumerate(__lowerCAmelCase			):
             UpperCamelCase_					: Union[str, Any]            =				idx
             UpperCamelCase_					: Optional[int]            =				i.val

       for i in range(__lowerCAmelCase      ,  -1      ,  -1			):
             self.sift_down(__lowerCAmelCase      ,  __lowerCAmelCase			)
       return array
 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase      ,  __lowerCAmelCase			):
       while True:
             UpperCamelCase_					: Tuple            =				self.get_left_child_idx(__lowerCAmelCase			)  # noqa: E741
             UpperCamelCase_					: int            =				self.get_right_child_idx(__lowerCAmelCase			)

             UpperCamelCase_					: Union[str, Any]            =				idx
             if l < len(__lowerCAmelCase			) and array[l] < array[idx]:
                   UpperCamelCase_					: Any            =				l
             if r < len(__lowerCAmelCase			) and array[r] < array[smallest]:
                   UpperCamelCase_					: Optional[Any]            =				r

             if smallest != idx:
                   UpperCamelCase_     ,      UpperCamelCase_					: Any            =				array[smallest], array[idx]
                   (
                       (
                       UpperCamelCase_
                   )     ,      (
                       UpperCamelCase_
                   )     ,      
                   )					: int            =				(
                       self.idx_of_element[array[smallest]],
                       self.idx_of_element[array[idx]],
                   )
                   UpperCamelCase_					: Optional[int]            =				smallest
             else:
                   break
 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase			):
       UpperCamelCase_					: List[Any]            =				self.get_parent_idx(__lowerCAmelCase			)
       while p >= 0 and self.heap[p] > self.heap[idx]:
             UpperCamelCase_     ,      UpperCamelCase_					: List[str]            =				self.heap[idx], self.heap[p]
             UpperCamelCase_     ,      UpperCamelCase_					: Optional[Any]            =				(
                 self.idx_of_element[self.heap[idx]],
                 self.idx_of_element[self.heap[p]],
             )
             UpperCamelCase_					: Any            =				p
             UpperCamelCase_					: Tuple            =				self.get_parent_idx(__lowerCAmelCase			)
 def 	_UpperCAmelCase							(				self			):
       return self.heap[0]
 def 	_UpperCAmelCase							(				self			):
       UpperCamelCase_     ,      UpperCamelCase_					: Any            =				self.heap[-1], self.heap[0]
       UpperCamelCase_     ,      UpperCamelCase_					: List[str]            =				(
           self.idx_of_element[self.heap[-1]],
           self.idx_of_element[self.heap[0]],
       )

       UpperCamelCase_					: str            =				self.heap.pop()
       del self.idx_of_element[x]
       self.sift_down(0      ,  self.heap			)
       return x
 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase			):
       self.heap.append(__lowerCAmelCase			)
       UpperCamelCase_					: Tuple            =				len(self.heap			) - 1
       UpperCamelCase_					: Tuple            =				node.val
       self.sift_up(len(self.heap			) - 1			)
 def 	_UpperCAmelCase							(				self			):
       return len(self.heap			) == 0





 def 	_UpperCAmelCase							(				self      ,  __lowerCAmelCase      ,  __lowerCAmelCase			):
       assert (
           self.heap[self.idx_of_element[node]].val > new_value
       ), "newValue must be less that current value"
       UpperCamelCase_					: List[Any]            =				new_value
       UpperCamelCase_					: Dict            =				new_value
       self.sift_up(self.idx_of_element[node]			)






UpperCamelCase      					=Node("R", -1)
UpperCamelCase      					=Node("B", 6)
UpperCamelCase      					=Node("A", 3)
UpperCamelCase      					=Node("X", 1)
UpperCamelCase      					=Node("E", 4)

# Use one of these two ways to generate Min-Heap

# Generating Min-Heap from array
UpperCamelCase      					=MinHeap([r, b, a, x, e])

# Generating Min-Heap by Insert method
# myMinHeap.insert(a)
# myMinHeap.insert(b)
# myMinHeap.insert(x)
# myMinHeap.insert(r)
# myMinHeap.insert(e)

# Before
print("Min Heap - before decrease key")
for i in my_min_heap.heap:
      print(i)

print("Min Heap - After decrease key of node [B -> -17]")
my_min_heap.decrease_key(b, -17)

# After
for i in my_min_heap.heap:
      print(i)

if __name__ == "__main__":
      import doctest

      doctest.testmod()














'''simple docstring'''

def 				snake_case       (  a_				:			list						)							->					list:





      """simple docstring"""

      UpperCamelCase_					: List[str]            =				False
      while is_sorted is False:  # Until all the indices are traversed keep looping
            UpperCamelCase_					: Tuple            =				True
            for i in range(0     , len(a_						) - 1     , 2						):  # iterating over all even indices
                  if input_list[i] > input_list[i + 1]:
                        UpperCamelCase_     ,      UpperCamelCase_					: Optional[Any]            =				input_list[i + 1], input_list[i]
                        # swapping if elements not in order
                        UpperCamelCase_					: Any            =				False

            for i in range(1     , len(a_						) - 1     , 2						):  # iterating over all odd indices
                  if input_list[i] > input_list[i + 1]:
                        UpperCamelCase_     ,      UpperCamelCase_					: List[str]            =				input_list[i + 1], input_list[i]
                        # swapping if elements not in order
                        UpperCamelCase_					: Dict            =				False
      return input_list


if __name__ == "__main__":
      print("Enter list to be sorted")
      UpperCamelCase      					=[int(x) for x in input().split()]
      # inputing elements of the list in one line
      UpperCamelCase      					=odd_even_sort(input_list)
      print("The sorted list is")
      print(sorted_list)






