






"""simple docstring"""


def        UpperCAmelCase      (					a__     ,      a__ ):





						'''simple docstring'''






						lowerCAmelCase   :Optional[Any]						=			0
						lowerCAmelCase   :Union[str, Any]						=			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

												lowerCAmelCase   :Optional[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

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


def        UpperCAmelCase      (					a__     ,      a__     ,      a__     ,      a__ ):





						'''simple docstring'''






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

						lowerCAmelCase   :str						=			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__ ):





						'''simple docstring'''






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


if __name__ == "__main__":
		import sys
		__SCREAMING_SNAKE_CASE   =   0
		if debug == 1:
				__SCREAMING_SNAKE_CASE   =   [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')
				__SCREAMING_SNAKE_CASE   =   67

		__SCREAMING_SNAKE_CASE   =   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__     ,      a__ ):





						'''simple docstring'''






						lowerCAmelCase   :Tuple						=			len(a__ )
						print('The following activities are selected:' )

						# The first activity is always selected
						lowerCAmelCase   :Dict						=			0
						print(a__     ,      end=',' )

						# Consider rest of the activities
						for j in range(a__ ):
												# If this activity has start time greater than
												# or equal to the finish time of previously
												# selected activity, then select it
												if start[j] >= finish[i]:
																		print(a__     ,      end=',' )
																		lowerCAmelCase   :List[str]						=			j


if __name__ == "__main__":
		import doctest

		doctest.testmod()

		__SCREAMING_SNAKE_CASE   =   [1, 3, 0, 5, 8, 5]
		__SCREAMING_SNAKE_CASE   =   [2, 4, 6, 7, 9, 9]
		print_max_activities(start, finish)