
from __future__ import annotations

# This is the precision for this function which can be altered.
# It is recommended for users to keep this number greater than or equal to 10.
lowerCamelCase__          =		10
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )				->		int:
			for i in range(SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     ):
						if array[i] == target:
									return i
			return -1
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )				->		int:
			lowerCAmelCase__      :      Optional[Any]         =		0
			lowerCAmelCase__      :      str         =		len(SCREAMING_SNAKE_CASE_     )
			while left <= right:
						if right - left < precision:
									return lin_search(SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )

						lowerCAmelCase__      :      List[str]         =		(left + right) // 3 + 1
						lowerCAmelCase__      :      List[Any]         =		2 * (left + right) // 3 + 1

						if array[one_third] == target:
									return one_third
						elif array[two_third] == target:
									return two_third

						elif target < array[one_third]:
									lowerCAmelCase__      :      int         =		one_third - 1
						elif array[two_third] < target:
									lowerCAmelCase__      :      List[str]         =		two_third + 1

						else:
									lowerCAmelCase__      :      Union[str, Any]         =		one_third + 1
									lowerCAmelCase__      :      Dict         =		two_third - 1
			else:
						return -1
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )				->		int:
			if left < right:
						if right - left < precision:
									return lin_search(SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )
						lowerCAmelCase__      :      List[str]         =		(left + right) // 3 + 1
						lowerCAmelCase__      :      Any         =		2 * (left + right) // 3 + 1

						if array[one_third] == target:
									return one_third
						elif array[two_third] == target:
									return two_third

						elif target < array[one_third]:
									return rec_ternary_search(SCREAMING_SNAKE_CASE_       ,							one_third - 1       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )
						elif array[two_third] < target:
									return rec_ternary_search(two_third + 1       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )
						else:
									return rec_ternary_search(one_third + 1       ,							two_third - 1       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )
			else:
						return -1


if __name__ == "__main__":
					import doctest

					doctest.testmod()

					lowerCamelCase__          =		input("""Enter numbers separated by comma:\n""").strip()
					lowerCamelCase__          =		[int(item.strip()) for item in user_input.split(""",""")]
					assert collection == sorted(collection), F"List must be ordered.\n{collection}."
					lowerCamelCase__          =		int(input("""Enter the number to be found in the list:\n""").strip())
					lowerCamelCase__          =		ite_ternary_search(collection, target)
					lowerCamelCase__          =		rec_ternary_search(0, len(collection) - 1, collection, target)
					if resulta != -1:
										print(F"""Iterative search: {target} found at positions: {resulta}""")
										print(F"""Recursive search: {target} found at positions: {resulta}""")
					else:
										print("""Not found""")

class      A__							:






				def __init__(						self					:      Optional[Any]    ,     a					:      list   ):






							'''simple docstring'''







							lowerCAmelCase__      :      Dict         =		set_counts
							lowerCAmelCase__      :      str         =		max(a   )
							lowerCAmelCase__      :      Any         =		len(a   )
							lowerCAmelCase__      :      List[str]         =		[1] * num_sets
							lowerCAmelCase__      :      Dict         =		list(range(a   )   )






				def 							_lowerCamelCase		(						self					:      Dict    ,     a					:      int    ,     a					:      int   ):






							'''simple docstring'''







							lowerCAmelCase__      :      Optional[Any]         =		self.get_parent(a   )
							lowerCAmelCase__      :      Tuple         =		self.get_parent(a   )

							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]
										lowerCAmelCase__      :      Tuple         =		0
										lowerCAmelCase__      :      str         =		dst_parent
										if self.ranks[dst_parent] == self.ranks[src_parent]:
													self.ranks[dst_parent] += 1
										lowerCAmelCase__      :      List[Any]         =		self.set_counts[dst_parent]
							else:
										self.set_counts[src_parent] += self.set_counts[dst_parent]
										lowerCAmelCase__      :      Optional[int]         =		0
										lowerCAmelCase__      :      Tuple         =		src_parent
										lowerCAmelCase__      :      Optional[int]         =		self.set_counts[src_parent]

							lowerCAmelCase__      :      Optional[Any]         =		max(self.max_set    ,     a   )
							return True






				def 							_lowerCamelCase		(						self					:      Any    ,     a					:      int   ):






							'''simple docstring'''







							if self.parents[disj_set] == disj_set:
										return disj_set
							lowerCAmelCase__      :      Tuple         =		self.get_parent(self.parents[disj_set]   )
							return self.parents[disj_set]