

from __future__ import annotations

import math

class __UpperCamelCase     :






					'''simple docstring'''



					def __init__(				self				,      lowerCamelCase__						):
						UpperCAmelCase__:	List[str]									= size
						# approximate the overall size of segment tree with given value
						UpperCAmelCase__:	Optional[int]									= [0 for i in range(0				,      4 * size						)]
						# create array to store lazy update
						UpperCAmelCase__:	List[str]									= [0 for i in range(0				,      4 * size						)]
						UpperCAmelCase__:	Union[str, Any]									= [0 for i in range(0				,      4 * size						)]  # flag for lazy update





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__						):
						return idx * 2





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__						):
						return idx * 2 + 1





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__						):
						if left_element == right_element:
							UpperCAmelCase__:	List[str]									= a[left_element - 1]
						else:
							UpperCAmelCase__:	Any									= (left_element + right_element) // 2
							self.build(self.left(lowerCamelCase__						)				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__						)
							self.build(self.right(lowerCamelCase__						)				,      mid + 1				,      lowerCamelCase__				,      lowerCamelCase__						)
							UpperCAmelCase__:	Union[str, Any]									= max(
							    self.segment_tree[self.left(lowerCamelCase__						)]				,      self.segment_tree[self.right(lowerCamelCase__						)]						)





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__						):
						if self.flag[idx] is True:
							UpperCAmelCase__:	List[Any]									= self.lazy[idx]
							UpperCAmelCase__:	Any									= False
							if left_element != right_element:
								UpperCAmelCase__:	Dict									= self.lazy[idx]
								UpperCAmelCase__:	str									= self.lazy[idx]
								UpperCAmelCase__:	Dict									= True
								UpperCAmelCase__:	Optional[Any]									= True

						if right_element < a or left_element > b:
							return True
						if left_element >= a and right_element <= b:
							UpperCAmelCase__:	int									= val
							if left_element != right_element:
								UpperCAmelCase__:	Optional[int]									= val
								UpperCAmelCase__:	Any									= val
								UpperCAmelCase__:	Tuple									= True
								UpperCAmelCase__:	Dict									= True
							return True
						UpperCAmelCase__:	Optional[int]									= (left_element + right_element) // 2
						self.update(self.left(lowerCamelCase__						)				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__						)
						self.update(self.right(lowerCamelCase__						)				,      mid + 1				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__						)
						UpperCAmelCase__:	List[Any]									= max(
						    self.segment_tree[self.left(lowerCamelCase__						)]				,      self.segment_tree[self.right(lowerCamelCase__						)]						)
						return True





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__						):
						if self.flag[idx] is True:
							UpperCAmelCase__:	Tuple									= self.lazy[idx]
							UpperCAmelCase__:	Optional[int]									= False
							if left_element != right_element:
								UpperCAmelCase__:	Dict									= self.lazy[idx]
								UpperCAmelCase__:	Any									= self.lazy[idx]
								UpperCAmelCase__:	Dict									= True
								UpperCAmelCase__:	Optional[Any]									= True
						if right_element < a or left_element > b:
							return -math.inf
						if left_element >= a and right_element <= b:
							return self.segment_tree[idx]
						UpperCAmelCase__:	Union[str, Any]									= (left_element + right_element) // 2
						UpperCAmelCase__:	Dict									= self.query(self.left(lowerCamelCase__						)				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__						)
						UpperCAmelCase__:	Any									= self.query(self.right(lowerCamelCase__						)				,      mid + 1				,      lowerCamelCase__				,      lowerCamelCase__				,      lowerCamelCase__						)
						return max(lowerCamelCase__				,      lowerCamelCase__						)





					def __str__(				self						):
						return str([self.query(1				,      1				,      self.size				,      lowerCamelCase__				,      lowerCamelCase__						) for i in range(1				,      self.size + 1						)]						)


if __name__ == "__main__":
					_lowerCAmelCase  :      int			 =[1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
					_lowerCAmelCase  :      int			 =15
					_lowerCAmelCase  :      int			 =SegmentTree(size)
					segt.build(1, 1, size, A)
					print(segt.query(1, 1, size, 4, 6))
					print(segt.query(1, 1, size, 7, 11))
					print(segt.query(1, 1, size, 7, 12))
					segt.update(1, 1, size, 1, 3, 1_11)
					print(segt.query(1, 1, size, 1, 15))
					segt.update(1, 1, size, 7, 8, 2_35)
					print(segt)


def 			_A	(      SCREAMING_SNAKE_CASE      ):
	UpperCAmelCase__							,						UpperCAmelCase__:	int									= [], []
	while len(SCREAMING_SNAKE_CASE      ) > 1:
		UpperCAmelCase__							,						UpperCAmelCase__:	str									= min(SCREAMING_SNAKE_CASE      ), max(SCREAMING_SNAKE_CASE      )
		start.append(SCREAMING_SNAKE_CASE      )
		end.append(SCREAMING_SNAKE_CASE      )
		collection.remove(SCREAMING_SNAKE_CASE      )
		collection.remove(SCREAMING_SNAKE_CASE      )
	end.reverse()
	return start + collection + end


if __name__ == "__main__":
					_lowerCAmelCase  :      Union[str, Any]			 =input("""Enter numbers separated by a comma:\n""").strip()
					_lowerCAmelCase  :      Dict			 =[int(item) for item in user_input.split(""",""")]
					print(*merge_sort(unsorted), sep=""",""")