
'''simple docstring'''



_lowercase    =		[0, 2, 4, 6, 8]
_lowercase    =		[1, 3, 5, 7, 9]


def A				(__lowerCamelCase				:int			,     __lowerCamelCase				:int			,     __lowerCamelCase				:list[int]			,     __lowerCamelCase				:int		):
						if remaining_length == 0:
												if digits[0] == 0 or digits[-1] == 0:
																		return 0

												for i in range(length // 2 - 1			,     -1			,     -1		):
																		remainder += digits[i] + digits[length - i - 1]

																		if remainder % 2 == 0:
																								return 0

																		remainder //= 10

												return 1

						if remaining_length == 1:
												if remainder % 2 == 0:
																		return 0

												_lowerCAmelCase  						=			0
												for digit in range(10		):
																		_lowerCAmelCase  						=			digit
																		result += reversible_numbers(
																		    0			,     (remainder + 2 * digit) // 10			,     __lowerCamelCase			,     __lowerCamelCase		)
												return result

						_lowerCAmelCase  						=			0
						for digita in range(10		):
												_lowerCAmelCase  						=			digita

												if (remainder + digita) % 2 == 0:
																		_lowerCAmelCase  						=			ODD_DIGITS
												else:
																		_lowerCAmelCase  						=			EVEN_DIGITS

												for digita in other_parity_digits:
																		_lowerCAmelCase  						=			digita
																		result += reversible_numbers(
																		    remaining_length - 2			,     (remainder + digita + digita) // 10			,     __lowerCamelCase			,     __lowerCamelCase			,     )
						return result


def A				(__lowerCamelCase				:int = 9		):
						_lowerCAmelCase  						=			0
						for length in range(1			,     max_power + 1		):
												result += reversible_numbers(__lowerCamelCase			,     0			,     [0] * length			,     __lowerCamelCase		)
						return result


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


'''simple docstring'''



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.
_lowercase    =		10


def A				(__lowerCamelCase				:int			,     __lowerCamelCase				:int			,     __lowerCamelCase				:list[int]			,     __lowerCamelCase				:int		):
						for i in range(__lowerCamelCase			,     __lowerCamelCase		):
												if array[i] == target:
																		return i
						return -1


def A				(__lowerCamelCase				:list[int]			,     __lowerCamelCase				:int		):
						_lowerCAmelCase  						=			0
						_lowerCAmelCase  						=			len(__lowerCamelCase		)
						while left <= right:
												if right - left < precision:
																		return lin_search(__lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase		)

												_lowerCAmelCase  						=			(left + right) // 3 + 1
												_lowerCAmelCase  						=			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  						=			one_third - 1
												elif array[two_third] < target:
																		_lowerCAmelCase  						=			two_third + 1

												else:
																		_lowerCAmelCase  						=			one_third + 1
																		_lowerCAmelCase  						=			two_third - 1
						else:
												return -1


def A				(__lowerCamelCase				:int			,     __lowerCamelCase				:int			,     __lowerCamelCase				:list[int]			,     __lowerCamelCase				:int		):
						if left < right:
												if right - left < precision:
																		return lin_search(__lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase		)
												_lowerCAmelCase  						=			(left + right) // 3 + 1
												_lowerCAmelCase  						=			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(__lowerCamelCase			,     one_third - 1			,     __lowerCamelCase			,     __lowerCamelCase		)
												elif array[two_third] < target:
																		return rec_ternary_search(two_third + 1			,     __lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase		)
												else:
																		return rec_ternary_search(one_third + 1			,     two_third - 1			,     __lowerCamelCase			,     __lowerCamelCase		)
						else:
												return -1


if __name__ == "__main__":
						import doctest

						doctest.testmod()

						_lowercase    =		input("""Enter numbers separated by comma:\n""").strip()
						_lowercase    =		[int(item.strip()) for item in user_input.split(""",""")]
						assert collection == sorted(collection), F"List must be ordered.\n{collection}."
						_lowercase    =		int(input("""Enter the number to be found in the list:\n""").strip())
						_lowercase    =		ite_ternary_search(collection, target)
						_lowercase    =		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""")
