



'''simple docstring'''



def        UpperCAmelCase (    A	:					List[str]       ,		A	:					int					):
							SCREAMING_SNAKE_CASE       :   Any         =      0
							SCREAMING_SNAKE_CASE       :   int         =      len(A					) - 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

														SCREAMING_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(A					):
																					return None

														SCREAMING_SNAKE_CASE       :   List[Any]         =      sorted_collection[point]
														if current_item == item:
																					return point
														else:
																					if point < left:
																												SCREAMING_SNAKE_CASE       :   Optional[Any]         =      left
																												SCREAMING_SNAKE_CASE       :   List[Any]         =      point
																					elif point > right:
																												SCREAMING_SNAKE_CASE       :   Optional[Any]         =      right
																												SCREAMING_SNAKE_CASE       :   List[str]         =      point
																					else:
																												if item < current_item:
																																			SCREAMING_SNAKE_CASE       :   str         =      point - 1
																												else:
																																			SCREAMING_SNAKE_CASE       :   List[Any]         =      point + 1
							return None
def        UpperCAmelCase (    A	:					Any       ,		A	:					List[Any]       ,		A	:					Optional[int]       ,		A	:					int					):

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

							SCREAMING_SNAKE_CASE       :   List[Any]         =      left + ((item - sorted_collection[left]) * (right - left)) // (
							    sorted_collection[right] - sorted_collection[left]
							)

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

							if sorted_collection[point] == item:
														return point
							elif point < left:
														return interpolation_search_by_recursion(A       ,		A       ,		A       ,		A					)
							elif point > right:
														return interpolation_search_by_recursion(A       ,		A       ,		A       ,		A					)
							else:
														if sorted_collection[point] > item:
																					return interpolation_search_by_recursion(
																					    A       ,		A       ,		A       ,		point - 1					)
														else:
																					return interpolation_search_by_recursion(
																					    A       ,		A       ,		point + 1       ,		A					)
def        UpperCAmelCase (    A	:					Dict					):
							if collection != sorted(A					):
														raise ValueError('''Collection must be ascending sorted'''					)
							return True


if __name__ == "__main__":
							import sys
							lowerCAmelCase_  :							List[Any]             =    0
							if debug == 1:
														lowerCAmelCase_  :							Any             =    [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')
														lowerCAmelCase_  :							Optional[Any]             =    67

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









'''simple docstring'''



def        UpperCAmelCase (    A	:					int       ,		A	:					int					):
							return x if y == 0 else greatest_common_divisor(A       ,		x % y					)
def        UpperCAmelCase (    A	:					int       ,		A	:					int					):
							return (x * y) // greatest_common_divisor(A       ,		A					)
def        UpperCAmelCase (    A	:					int = 20					):
							SCREAMING_SNAKE_CASE       :   Tuple         =      1
							for i in range(1       ,		n + 1					):
														SCREAMING_SNAKE_CASE       :   Optional[int]         =      lcm(A       ,		A					)
							return g


if __name__ == "__main__":
							print(f'{solution() = }')




