





def 						lowerCamelCase__     (     UpperCamelCase__			:       int       ,    UpperCamelCase__			:       list						)			-> Tuple:



					'''simple docstring'''




					_enforce_args(UpperCamelCase__       ,    UpperCamelCase__						)
					if n == 0:
										return 0
					_snake_case									=				float('-inf'						)
					for i in range(1       ,    n + 1						):
										_snake_case									=				max(
										    UpperCamelCase__       ,    prices[i - 1] + naive_cut_rod_recursive(n - i       ,    UpperCamelCase__						)						)

					return max_revue





def 						lowerCamelCase__     (     UpperCamelCase__			:       int       ,    UpperCamelCase__			:       list						)			-> str:



					'''simple docstring'''




					_enforce_args(UpperCamelCase__       ,    UpperCamelCase__						)
					_snake_case									=				[float('-inf'						) for _ in range(n + 1						)]
					return _top_down_cut_rod_recursive(UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__						)





def 						lowerCamelCase__     (     UpperCamelCase__			:       int       ,    UpperCamelCase__			:       list       ,    UpperCamelCase__			:       list						)			-> Union[str, Any]:



					'''simple docstring'''




					if max_rev[n] >= 0:
										return max_rev[n]
					elif n == 0:
										return 0
					else:
										_snake_case									=				float('-inf'						)
										for i in range(1       ,    n + 1						):
															_snake_case									=				max(
															    UpperCamelCase__       ,    prices[i - 1] + _top_down_cut_rod_recursive(n - i       ,    UpperCamelCase__       ,    UpperCamelCase__						)       ,    )

										_snake_case									=				max_revenue

					return max_rev[n]





def 						lowerCamelCase__     (     UpperCamelCase__			:       int       ,    UpperCamelCase__			:       list						)			-> Union[str, Any]:



					'''simple docstring'''




					_enforce_args(UpperCamelCase__       ,    UpperCamelCase__						)

					# length(max_rev) = n + 1, to accommodate for the revenue obtainable from a rod of
					# length 0.
					_snake_case									=				[float('-inf'						) for _ in range(n + 1						)]
					_snake_case									=				0

					for i in range(1       ,    n + 1						):
										_snake_case									=				max_rev[i]
										for j in range(1       ,    i + 1						):
															_snake_case									=				max(UpperCamelCase__       ,    prices[j - 1] + max_rev[i - j]						)

										_snake_case									=				max_revenue_i

					return max_rev[n]





def 						lowerCamelCase__     (     UpperCamelCase__			:       int       ,    UpperCamelCase__			:       list						)			-> Tuple:



					'''simple docstring'''




					if n < 0:
										_snake_case									=				F'''n must be greater than or equal to 0. Got n = {n}'''
										raise ValueError(UpperCamelCase__						)

					if n > len(UpperCamelCase__						):
										_snake_case									=				(
										    'Each integral piece of rod must have a corresponding price. '
										    F'''Got n = {n} but length of prices = {len(UpperCamelCase__						)}'''
										)
										raise ValueError(UpperCamelCase__						)





def 						lowerCamelCase__     (     )			-> Optional[int]:



					'''simple docstring'''




					_snake_case									=				[6, 10, 12, 15, 20, 23]
					_snake_case									=				len(UpperCamelCase__						)

					# the best revenue comes from cutting the rod into 6 pieces, each
					# of length 1 resulting in a revenue of 6 * 6 = 36.
					_snake_case									=				36

					_snake_case									=				top_down_cut_rod(UpperCamelCase__       ,    UpperCamelCase__						)
					_snake_case									=				bottom_up_cut_rod(UpperCamelCase__       ,    UpperCamelCase__						)
					_snake_case									=				naive_cut_rod_recursive(UpperCamelCase__       ,    UpperCamelCase__						)

					assert expected_max_revenue == max_rev_top_down
					assert max_rev_top_down == max_rev_bottom_up
					assert max_rev_bottom_up == max_rev_naive


if __name__ == "__main__":
					main()










def 						lowerCamelCase__     (     UpperCamelCase__			:       list						)			-> list:



					'''simple docstring'''




					_snake_case									=				len(UpperCamelCase__						)
					for i in range(1       ,    UpperCamelCase__						):
										_snake_case									=				collection[i]
										_snake_case									=				0
										_snake_case									=				i - 1

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


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



