



"""simple docstring"""

def 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  Any				,    SCREAMING_SNAKE_CASE__ :  List[str]			):



					"""simple docstring"""





					snake_case_					:		Optional[Any] 					=					0
					snake_case_					:		int 					=					len(SCREAMING_SNAKE_CASE__			) - 1

					while left <= right:
										# avoid divided by 0 during interpolation
										if sorted_collection[left] == sorted_collection[right]:
															if sorted_collection[left] == item:
																				return left
															else:
																				return None

										snake_case_					:		Optional[int] 					=					left + ((item - sorted_collection[left]) * (right - left)) // (
										    sorted_collection[right] - sorted_collection[left]
										)

										# out of range check
										if point < 0 or point >= len(SCREAMING_SNAKE_CASE__			):
															return None

										snake_case_					:		Dict 					=					sorted_collection[point]
										if current_item == item:
															return point
										else:
															if point < left:
																				snake_case_					:		List[Any] 					=					left
																				snake_case_					:		List[Any] 					=					point
															elif point > right:
																				snake_case_					:		List[Any] 					=					right
																				snake_case_					:		Tuple 					=					point
															else:
																				if item < current_item:
																									snake_case_					:		List[Any] 					=					point - 1
																				else:
																									snake_case_					:		Union[str, Any] 					=					point + 1
					return None







def 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  str				,    SCREAMING_SNAKE_CASE__ :  Tuple				,    SCREAMING_SNAKE_CASE__ :  int				,    SCREAMING_SNAKE_CASE__ :  Optional[Any]			):



					"""simple docstring"""





					if sorted_collection[left] == sorted_collection[right]:
										if sorted_collection[left] == item:
															return left
										else:
															return None

					snake_case_					:		int 					=					left + ((item - sorted_collection[left]) * (right - left)) // (
					    sorted_collection[right] - sorted_collection[left]
					)

					# out of range check
					if point < 0 or point >= len(SCREAMING_SNAKE_CASE__			):
										return None

					if sorted_collection[point] == item:
										return point
					elif point < left:
										return interpolation_search_by_recursion(SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__			)
					elif point > right:
										return interpolation_search_by_recursion(SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__			)
					else:
										if sorted_collection[point] > item:
															return interpolation_search_by_recursion(
															    SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__				,    point - 1			)
										else:
															return interpolation_search_by_recursion(
															    SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__				,    point + 1				,    SCREAMING_SNAKE_CASE__			)







def 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  Any			):



					"""simple docstring"""





					if collection != sorted(SCREAMING_SNAKE_CASE__			):
										raise ValueError("""Collection must be ascending sorted"""			)
					return True


if __name__ == "__main__":
			import sys
			a_			   =					0
			if debug == 1:
						a_			   =					[10, 30, 40, 45, 50, 66, 77, 93]
						try:
									__assert_sorted(collection)
						except ValueError:
									sys.exit('''Sequence must be ascending sorted to apply interpolation search''')
						a_			   =					67

			a_			   =					interpolation_search(collection, target)
			if result is not None:
						print(F'''{target} found at positions: {result}''')
			else:
						print('''Not found''')









"""simple docstring"""

def 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  list			):



					"""simple docstring"""





					snake_case_					:		Optional[int] 					=					len(SCREAMING_SNAKE_CASE__			)
					for i in range(1				,    SCREAMING_SNAKE_CASE__			):
										snake_case_					:		Tuple 					=					collection[i]
										snake_case_					:		Tuple 					=					0
										snake_case_					:		str 					=					i - 1

										while low <= high:
															snake_case_					:		Optional[int] 					=					(low + high) // 2
															if val < collection[mid]:
																				snake_case_					:		List[str] 					=					mid - 1
															else:
																				snake_case_					:		str 					=					mid + 1
										for j in range(SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__				,    -1			):
															snake_case_					:		List[str] 					=					collection[j - 1]
										snake_case_					:		Any 					=					val
					return collection


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




