


"""simple docstring"""






from __future__ import annotations

from typing import Generic, TypeVar

_lowerCAmelCase							:    Union[str, Any]					   =	TypeVar('''T''')




class 							A_      (       Generic[T] ):


  def __init__(			self:						Optional[Any]							,__lowerCAmelCase:						T    ):







     '''simple docstring'''







     _lowerCamelCase   :				Tuple							=     data
     _lowerCamelCase   :				int							=     self
     _lowerCamelCase   :				Optional[int]							=     0




class 							A_      (       Generic[T] ):


  def __init__(			self:						Tuple    ):







     '''simple docstring'''







     _lowerCamelCase   :				dict[T, DisjointSetTreeNode[T]]							=     {}


  def 							_lowercase					(			self:						Any							,__lowerCAmelCase:						T    ):







     '''simple docstring'''







     _lowerCamelCase   :				List[Any]							=     DisjointSetTreeNode(__lowerCAmelCase    )


  def 							_lowercase					(			self:						Optional[Any]							,__lowerCAmelCase:						T    ):







     '''simple docstring'''







     _lowerCamelCase   :				Optional[int]							=     self.map[data]
     if elem_ref != elem_ref.parent:
        _lowerCamelCase   :				Union[str, Any]							=     self.find_set(elem_ref.parent.data    )
     return elem_ref.parent


  def 							_lowercase					(			self:						Optional[Any]							,__lowerCAmelCase:						DisjointSetTreeNode[T]							,__lowerCAmelCase:						DisjointSetTreeNode[T]    ):







     '''simple docstring'''







     if nodea.rank > nodea.rank:
        _lowerCamelCase   :				Tuple							=     nodea
     else:
        _lowerCamelCase   :				Optional[int]							=     nodea
        if nodea.rank == nodea.rank:
           nodea.rank += 1






  def 							_lowercase					(			self:						Any							,__lowerCAmelCase:						T							,__lowerCAmelCase:						T    ):







     '''simple docstring'''







     self.link(self.find_set(__lowerCAmelCase    )							,self.find_set(__lowerCAmelCase    )    )




class 							A_      (       Generic[T] ):


  def __init__(			self:						Tuple    ):







     '''simple docstring'''







     _lowerCamelCase   :				dict[T, dict[T, int]]							=     {}


  def 							_lowercase					(			self:						Tuple							,__lowerCAmelCase:						T    ):







     '''simple docstring'''







     if node not in self.connections:
        _lowerCamelCase   :				List[str]							=     {}


  def 							_lowercase					(			self:						Optional[int]							,__lowerCAmelCase:						T							,__lowerCAmelCase:						T							,__lowerCAmelCase:						int    ):







     '''simple docstring'''







     self.add_node(__lowerCAmelCase    )
     self.add_node(__lowerCAmelCase    )
     _lowerCamelCase   :				Dict							=     weight
     _lowerCamelCase   :				Dict							=     weight






  def 							_lowercase					(			self:						str    ):







     '''simple docstring'''







     _lowerCamelCase   :				Any							=     []
     _lowerCamelCase   :				Optional[int]							=     set()
     for start in self.connections:
        for end in self.connections[start]:
           if (start, end) not in seen:
              seen.add((end, start)    )
              edges.append((start, end, self.connections[start][end])    )
     edges.sort(key=lambda __lowerCAmelCase    : x[2]    )

     # creating the disjoint set
     _lowerCamelCase   :				str							=     DisjointSetTree[T]()
     for node in self.connections:
        disjoint_set.make_set(__lowerCAmelCase    )

     # MST generation
     _lowerCamelCase   :				Tuple							=     0
     _lowerCamelCase   :				List[str]							=     0
     _lowerCamelCase   :				int							=     GraphUndirectedWeighted[T]()
     while num_edges < len(self.connections    ) - 1:
        _lowerCamelCase,					_lowerCamelCase,					_lowerCamelCase   :				Optional[Any]							=     edges[index]
        index += 1
        _lowerCamelCase   :				Union[str, Any]							=     disjoint_set.find_set(__lowerCAmelCase    )
        _lowerCamelCase   :				Tuple							=     disjoint_set.find_set(__lowerCAmelCase    )
        if parent_u != parent_v:
           num_edges += 1
           graph.add_edge(__lowerCAmelCase							,__lowerCAmelCase							,__lowerCAmelCase    )
           disjoint_set.union(__lowerCAmelCase							,__lowerCAmelCase    )
     return graph


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

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


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



