


'''simple docstring'''

def __snake_case      (   UpperCAmelCase_		:		list					):
 lowerCamelCase_  				=						len(UpperCAmelCase__					)
 for i in range(1      ,       UpperCAmelCase__					):
  lowerCamelCase_  				=						collection[i]
  lowerCamelCase_  				=						0
  lowerCamelCase_  				=						i - 1

  while low <= high:
   lowerCamelCase_  				=						(low + high) // 2
   if val < collection[mid]:
    lowerCamelCase_  				=						mid - 1
   else:
    lowerCamelCase_  				=						mid + 1
  for j in range(UpperCAmelCase__      ,       UpperCAmelCase__      ,       -1					):
   lowerCamelCase_  				=						collection[j - 1]
  lowerCamelCase_  				=						val
 return collection


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







'''simple docstring'''

from __future__ import annotations





def __snake_case      (   UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int	):
 if b == 0:
  return (1, 0)
 ((lowerCamelCase_)				,(lowerCamelCase_))  				=						extended_euclid(UpperCAmelCase_      ,       a % b	)
 lowerCamelCase_  				=						a // b
 return (y, x - k * y)





def __snake_case      (   UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int	):
 ((lowerCamelCase_)				,(lowerCamelCase_))  				=						extended_euclid(UpperCAmelCase_      ,       UpperCAmelCase_	)
 lowerCamelCase_  				=						na * na
 lowerCamelCase_  				=						ra * x * na + ra * y * na
 return (n % m + m) % m





def __snake_case      (   UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int	):
 ((lowerCamelCase_)				,(lowerCamelCase_))  				=						extended_euclid(UpperCAmelCase_      ,       UpperCAmelCase_	)
 if b < 0:
  lowerCamelCase_  				=						(b % n + n) % n
 return b





def __snake_case      (   UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int	):
 lowerCamelCase_				,lowerCamelCase_  				=						invert_modulo(UpperCAmelCase_      ,       UpperCAmelCase_	), invert_modulo(UpperCAmelCase_      ,       UpperCAmelCase_	)
 lowerCamelCase_  				=						na * na
 lowerCamelCase_  				=						ra * x * na + ra * y * na
 return (n % m + m) % m


if __name__ == "__main__":
     from doctest import testmod

     testmod(name="""chinese_remainder_theorem""", verbose=True)
     testmod(name="""chinese_remainder_theorem2""", verbose=True)
     testmod(name="""invert_modulo""", verbose=True)
     testmod(name="""extended_euclid""", verbose=True)



