



"""simple docstring"""





class  _lowerCAmelCase     :





		"""simple docstring"""






		def __init__(       self				,     _lowercase )			->    None:







								'''simple docstring'''

								snake_case_ :			List[str]            =      set_counts
								snake_case_ :			str            =      max(_lowercase )
								snake_case_ :			Any            =      len(_lowercase )
								snake_case_ :			Any            =      [1] * num_sets
								snake_case_ :			List[Any]            =      list(range(_lowercase ) )





		def  UpperCAmelCase__				(       self				,     _lowercase				,     _lowercase )			->    bool:







								'''simple docstring'''

								snake_case_ :			List[str]            =      self.get_parent(_lowercase )
								snake_case_ :			Tuple            =      self.get_parent(_lowercase )

								if src_parent == dst_parent:
														return False

								if self.ranks[dst_parent] >= self.ranks[src_parent]:
														self.set_counts[dst_parent] += self.set_counts[src_parent]
														snake_case_ :			Tuple            =      0
														snake_case_ :			Any            =      dst_parent
														if self.ranks[dst_parent] == self.ranks[src_parent]:
																				self.ranks[dst_parent] += 1
														snake_case_ :			Optional[int]            =      self.set_counts[dst_parent]
								else:
														self.set_counts[src_parent] += self.set_counts[dst_parent]
														snake_case_ :			int            =      0
														snake_case_ :			Optional[Any]            =      src_parent
														snake_case_ :			Union[str, Any]            =      self.set_counts[src_parent]

								snake_case_ :			Union[str, Any]            =      max(self.max_set				,     _lowercase )
								return True





		def  UpperCAmelCase__				(       self				,     _lowercase )			->    int:







								'''simple docstring'''

								if self.parents[disj_set] == disj_set:
														return disj_set
								snake_case_ :			Union[str, Any]            =      self.get_parent(self.parents[disj_set] )
								return self.parents[disj_set]






def  lowerCAmelCase_	(lowerCAmelCase__:		Union[str, Any]		,						lowerCAmelCase__:		Optional[int]  ):





			"""simple docstring"""


			UpperCAmelCase_:		List[str]							      =     0
			UpperCAmelCase_:		Tuple							      =     len(lowerCAmelCase__  ) - 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

						UpperCAmelCase_:		Dict							      =     left + ((item - sorted_collection[left]) * (right - left)) // (
						    sorted_collection[right] - sorted_collection[left]
						)

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

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







def  lowerCAmelCase_	(lowerCAmelCase__:		Dict		,						lowerCAmelCase__:		List[Any]		,						lowerCAmelCase__:		Any		,						lowerCAmelCase__:		Any  ):





			"""simple docstring"""


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

			UpperCAmelCase_:		Union[str, Any]							      =     left + ((item - sorted_collection[left]) * (right - left)) // (
			    sorted_collection[right] - sorted_collection[left]
			)

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

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







def  lowerCAmelCase_	(lowerCAmelCase__:		Dict  ):





			"""simple docstring"""


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


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

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






