


from __future__ import annotations

from collections import defaultdict
from dataclasses import dataclass



@dataclass
class  UpperCAmelCase_						:
       '''simple docstring'''
       __UpperCamelCase   :  int
       __UpperCamelCase   :  TreeNode | None				=       None
       __UpperCamelCase   :  TreeNode | None				=       None




def   a						(				):






       """simple docstring"""





       return TreeNode(3				,      TreeNode(9							)				,      TreeNode(2_0				,      TreeNode(1_5							)				,      TreeNode(7							)							)							)


def   a						(				SCREAMING_SNAKE_CASE_   :		int							):






       """simple docstring"""





       def depth_first_search(
           SCREAMING_SNAKE_CASE_   :		Tuple				,      SCREAMING_SNAKE_CASE_   :		Any				,      SCREAMING_SNAKE_CASE_   :		Tuple							) -> None:
              if not root:
                     return

              if depth == len(snake_case__							):
                     right_view.append(root.val							)

              depth_first_search(root.right				,      depth + 1				,      snake_case__							)
              depth_first_search(root.left				,      depth + 1				,      snake_case__							)

       UpperCamelCase     :						Any 						=		[]
       if not root:
              return right_view

       depth_first_search(snake_case__				,      0				,      snake_case__							)
       return right_view


def   a						(				SCREAMING_SNAKE_CASE_   :		Union[str, Any]							):






       """simple docstring"""





       def depth_first_search(
           SCREAMING_SNAKE_CASE_   :		str				,      SCREAMING_SNAKE_CASE_   :		str				,      SCREAMING_SNAKE_CASE_   :		Optional[int]							) -> None:
              if not root:
                     return

              if depth == len(snake_case__							):
                     left_view.append(root.val							)

              depth_first_search(root.left				,      depth + 1				,      snake_case__							)
              depth_first_search(root.right				,      depth + 1				,      snake_case__							)

       UpperCamelCase     :						Union[str, Any] 						=		[]
       if not root:
              return left_view

       depth_first_search(snake_case__				,      0				,      snake_case__							)
       return left_view


def   a						(				SCREAMING_SNAKE_CASE_   :		int							):






       """simple docstring"""





       def breadth_first_search(SCREAMING_SNAKE_CASE_   :		Union[str, Any]				,      SCREAMING_SNAKE_CASE_   :		Optional[Any]							) -> None:
              UpperCamelCase     :						Dict 						=		[(root, 0)]
              UpperCamelCase     :						List[str] 						=		defaultdict(snake_case__							)

              while queue:
                     UpperCamelCase     :						str 						=		queue.pop(0							)
                     UpperCamelCase						,			UpperCamelCase     :						str 						=		first

                     lookup[hd].append(node.val							)

                     if node.left:
                            queue.append((node.left, hd - 1)							)
                     if node.right:
                            queue.append((node.right, hd + 1)							)

              for pair in sorted(lookup.items()				,      key=lambda SCREAMING_SNAKE_CASE_							: each[0]							):
                     top_view.append(pair[1][0]							)

       UpperCamelCase     :						Any 						=		[]
       if not root:
              return top_view

       breadth_first_search(snake_case__				,      snake_case__							)
       return top_view


def   a						(				SCREAMING_SNAKE_CASE_   :		Optional[int]							):






       """simple docstring"""





       from collections import defaultdict

       def breadth_first_search(SCREAMING_SNAKE_CASE_   :		int				,      SCREAMING_SNAKE_CASE_   :		Dict							) -> None:
              UpperCamelCase     :						List[str] 						=		[(root, 0)]
              UpperCamelCase     :						Optional[int] 						=		defaultdict(snake_case__							)

              while queue:
                     UpperCamelCase     :						Optional[Any] 						=		queue.pop(0							)
                     UpperCamelCase						,			UpperCamelCase     :						List[str] 						=		first
                     lookup[hd].append(node.val							)

                     if node.left:
                            queue.append((node.left, hd - 1)							)
                     if node.right:
                            queue.append((node.right, hd + 1)							)

              for pair in sorted(lookup.items()				,      key=lambda SCREAMING_SNAKE_CASE_							: each[0]							):
                     bottom_view.append(pair[1][-1]							)

       UpperCamelCase     :						List[str] 						=		[]
       if not root:
              return bottom_view

       breadth_first_search(snake_case__				,      snake_case__							)
       return bottom_view


if __name__ == "__main__":
  import doctest

  doctest.testmod()









from __future__ import annotations

def 			__lowerCamelCase     (						snake_case__			,snake_case__						)				->    Dict:






						"""simple docstring"""





						_SCREAMING_SNAKE_CASE       =    0
						_SCREAMING_SNAKE_CASE       =    len(snake_case__						) - 1
						while left <= right:
												_SCREAMING_SNAKE_CASE       =    (left + right) // 2
												if left == right:
																		if sorted_list[middle] < item:
																								_SCREAMING_SNAKE_CASE       =    middle + 1
																		break
												elif sorted_list[middle] < item:
																		_SCREAMING_SNAKE_CASE       =    middle + 1
												else:
																		_SCREAMING_SNAKE_CASE       =    middle - 1
						sorted_list.insert(snake_case__			,snake_case__						)
						return sorted_list

def 			__lowerCamelCase     (						snake_case__			,snake_case__						)				->    Optional[Any]:






						"""simple docstring"""





						_SCREAMING_SNAKE_CASE       =    []
						while left and right:
												if left[0][0] < right[0][0]:
																		result.append(left.pop(0						)						)
												else:
																		result.append(right.pop(0						)						)
						return result + left + right

def 			__lowerCamelCase     (						snake_case__						)				->    List[str]:






						"""simple docstring"""





						_SCREAMING_SNAKE_CASE       =    len(snake_case__						)
						if length <= 1:
												return list_ad
						_SCREAMING_SNAKE_CASE       =    length // 2
						return merge(sortlist_ad(list_ad[:middle]						)			,sortlist_ad(list_ad[middle:]						)						)

def 			__lowerCamelCase     (						snake_case__						)				->    list[int]:






						"""simple docstring"""





						if len(snake_case__						) <= 1:
												return collection
						_SCREAMING_SNAKE_CASE       =    []
						_SCREAMING_SNAKE_CASE       =    False
						for i in range(0			,len(snake_case__						)			,2						):
												if i == len(snake_case__						) - 1:
																		_SCREAMING_SNAKE_CASE       =    True
												else:
																		if collection[i] < collection[i + 1]:
																								two_paired_list.append([collection[i], collection[i + 1]]						)
																		else:
																								two_paired_list.append([collection[i + 1], collection[i]]						)
						_SCREAMING_SNAKE_CASE       =    sortlist_ad(snake_case__						)
						_SCREAMING_SNAKE_CASE       =    [i[0] for i in sorted_list_ad]
						result.append(sorted_list_ad[-1][1]						)
						if has_last_odd_item:
												_SCREAMING_SNAKE_CASE       =    collection[-1]
												_SCREAMING_SNAKE_CASE       =    binary_search_insertion(snake_case__			,snake_case__						)
						_SCREAMING_SNAKE_CASE       =    False
						for i in range(len(snake_case__						) - 1						):
												if result[i] == collection[-1] and has_last_odd_item:
																		_SCREAMING_SNAKE_CASE       =    True
												_SCREAMING_SNAKE_CASE       =    sorted_list_ad[i][1]
												# If last_odd_item is inserted before the item's index,
												# you should forward index one more.
												if is_last_odd_item_inserted_before_this_index:
																		_SCREAMING_SNAKE_CASE       =    result[: i + 2] + binary_search_insertion(result[i + 2 :]			,snake_case__						)
												else:
																		_SCREAMING_SNAKE_CASE       =    result[: i + 1] + binary_search_insertion(result[i + 1 :]			,snake_case__						)

						return result


if __name__ == "__main__":
		UpperCamelCase												=      input('''Enter numbers separated by a comma:\n''').strip()
		UpperCamelCase												=      [int(item) for item in user_input.split(''',''')]
		print(merge_insertion_sort(unsorted))

