





"""simple docstring"""




from __future__ import annotations





def 						UpperCAmelCase__		(					_UpperCAmelCase			, _UpperCAmelCase ):






  """simple docstring"""





  A_  :	int    						=  0
  A_  :	str    						=  len(_UpperCAmelCase ) - 1
  while left <= right:
    A_  :	Any    						=  (left + right) // 2
    if left == right:
      if sorted_list[middle] < item:
        A_  :	Optional[Any]    						=  middle + 1
      break
    elif sorted_list[middle] < item:
      A_  :	Tuple    						=  middle + 1
    else:
      A_  :	List[Any]    						=  middle - 1
  sorted_list.insert(_UpperCAmelCase			, _UpperCAmelCase )
  return sorted_list





def 						UpperCAmelCase__		(					_UpperCAmelCase			, _UpperCAmelCase ):






  """simple docstring"""





  A_  :	str    						=  []
  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 						UpperCAmelCase__		(					_UpperCAmelCase ):






  """simple docstring"""





  A_  :	Union[str, Any]    						=  len(_UpperCAmelCase )
  if length <= 1:
    return list_ad
  A_  :	int    						=  length // 2
  return merge(sortlist_ad(list_ad[:middle] )			, sortlist_ad(list_ad[middle:] ) )





def 						UpperCAmelCase__		(					_UpperCAmelCase ):






  """simple docstring"""





  if len(_UpperCAmelCase ) <= 1:
    return collection
  A_  :	Optional[int]    						=  []
  A_  :	int    						=  False
  for i in range(0			, len(_UpperCAmelCase )			, 2 ):
    if i == len(_UpperCAmelCase ) - 1:
      A_  :	str    						=  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]] )
  A_  :	Union[str, Any]    						=  sortlist_ad(_UpperCAmelCase )
  A_  :	List[Any]    						=  [i[0] for i in sorted_list_ad]
  result.append(sorted_list_ad[-1][1] )
  if has_last_odd_item:
    A_  :	Tuple    						=  collection[-1]
    A_  :	Optional[Any]    						=  binary_search_insertion(_UpperCAmelCase			, _UpperCAmelCase )
  A_  :	Optional[int]    						=  False
  for i in range(len(_UpperCAmelCase ) - 1 ):
    if result[i] == collection[-1] and has_last_odd_item:
      A_  :	Any    						=  True
    A_  :	List[str]    						=  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:
      A_  :	Dict    						=  result[: i + 2] + binary_search_insertion(result[i + 2 :]			, _UpperCAmelCase )
    else:
      A_  :	str    						=  result[: i + 1] + binary_search_insertion(result[i + 1 :]			, _UpperCAmelCase )

  return result


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






"""simple docstring"""




def 						UpperCAmelCase__		(					_UpperCAmelCase			, _UpperCAmelCase ):






  """simple docstring"""





  A_  :	Any    						=  len(_UpperCAmelCase )
  # Create a stack and push index of fist element to it
  A_  :	List[Any]    						=  []
  st.append(0 )

  # Span value of first element is always 1
  A_  :	List[str]    						=  1

  # Calculate span values for rest of the elements
  for i in range(1			, _UpperCAmelCase ):
    # Pop elements from stack while stack is not
    # empty and top of stack is smaller than price[i]
    while len(_UpperCAmelCase ) > 0 and price[st[0]] <= price[i]:
      st.pop()

    # If stack becomes empty, then price[i] is greater
    # than all elements on left of it, i.e. price[0],
    # price[1], ..price[i-1]. Else the price[i]  is
    # greater than elements after top of stack
    A_  :	Union[str, Any]    						=  i + 1 if len(_UpperCAmelCase ) <= 0 else (i - st[0])

    # Push this element to stack
    st.append(_UpperCAmelCase )





def 						UpperCAmelCase__		(					_UpperCAmelCase			, _UpperCAmelCase ):






  """simple docstring"""





  for i in range(0			, _UpperCAmelCase ):
    print(arr[i]			, end=' ' )


# Driver program to test above function
lowerCamelCase_					:						List[Any]      = [10, 4, 5, 90, 1_20, 80]
lowerCamelCase_					:						Optional[Any]      = [0 for i in range(len(price) + 1)]

# Fill the span values in array S[]
calculation_span(price, S)





print_array(S, len(price))