




'''simple docstring'''



import numpy as np

UpperCamelCase_    	=				[
    ["a", "b", "c", "d", "e"],
    ["f", "g", "h", "i", "k"],
    ["l", "m", "n", "o", "p"],
    ["q", "r", "s", "t", "u"],
    ["v", "w", "x", "y", "z"],
]






class 							_a				:





       '''simple docstring'''






       def __init__(      self  ):







             '''simple docstring'''







             SCREAMING_SNAKE_CASE   :      Tuple    					=						np.array(A  )







       def        UpperCamelCase_							(      self,							A  ):







             '''simple docstring'''







             SCREAMING_SNAKE_CASE					,    SCREAMING_SNAKE_CASE   :      Optional[int]    					=						np.where(letter == self.SQUARE  )
             SCREAMING_SNAKE_CASE   :      List[Any]    					=						np.concatenate([indexa + 1, indexa + 1]  )
             return indexes







       def        UpperCamelCase_							(      self,							A,							A  ):







             '''simple docstring'''







             SCREAMING_SNAKE_CASE   :      Optional[int]    					=						self.SQUARE[indexa - 1, indexa - 1]
             return letter







       def        UpperCamelCase_							(      self,							A  ):







             '''simple docstring'''







             SCREAMING_SNAKE_CASE   :      Any    					=						message.lower()
             SCREAMING_SNAKE_CASE   :      List[Any]    					=						message.replace(' ',							''  )
             SCREAMING_SNAKE_CASE   :      Optional[int]    					=						message.replace('j',							'i'  )

             SCREAMING_SNAKE_CASE   :      Dict    					=						np.empty((2, len(A  ))  )
             for letter_index in range(len(A  )  ):
                   SCREAMING_SNAKE_CASE   :      Optional[int]    					=						self.letter_to_numbers(message[letter_index]  )

                   SCREAMING_SNAKE_CASE   :      Tuple    					=						numbers[0]
                   SCREAMING_SNAKE_CASE   :      str    					=						numbers[1]

             SCREAMING_SNAKE_CASE   :      Any    					=						first_step.reshape(2 * len(A  )  )
             SCREAMING_SNAKE_CASE   :      Tuple    					=						''
             for numbers_index in range(len(A  )  ):
                   SCREAMING_SNAKE_CASE   :      List[Any]    					=						int(second_step[numbers_index * 2]  )
                   SCREAMING_SNAKE_CASE   :      Dict    					=						int(second_step[(numbers_index * 2) + 1]  )
                   SCREAMING_SNAKE_CASE   :      Optional[Any]    					=						self.numbers_to_letter(A,							A  )
                   SCREAMING_SNAKE_CASE   :      Dict    					=						encoded_message + letter

             return encoded_message







       def        UpperCamelCase_							(      self,							A  ):







             '''simple docstring'''







             SCREAMING_SNAKE_CASE   :      str    					=						message.lower()
             message.replace(' ',							''  )
             SCREAMING_SNAKE_CASE   :      int    					=						np.empty(2 * len(A  )  )
             for letter_index in range(len(A  )  ):
                   SCREAMING_SNAKE_CASE   :      Tuple    					=						self.letter_to_numbers(message[letter_index]  )
                   SCREAMING_SNAKE_CASE   :      str    					=						numbers[0]
                   SCREAMING_SNAKE_CASE   :      Dict    					=						numbers[1]

             SCREAMING_SNAKE_CASE   :      str    					=						first_step.reshape((2, len(A  ))  )
             SCREAMING_SNAKE_CASE   :      Any    					=						''
             for numbers_index in range(len(A  )  ):
                   SCREAMING_SNAKE_CASE   :      Any    					=						int(second_step[0, numbers_index]  )
                   SCREAMING_SNAKE_CASE   :      Union[str, Any]    					=						int(second_step[1, numbers_index]  )
                   SCREAMING_SNAKE_CASE   :      Any    					=						self.numbers_to_letter(A,							A  )
                   SCREAMING_SNAKE_CASE   :      Dict    					=						decoded_message + letter

             return decoded_message



'''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.
__snake_case						  =		10

def   A_      (       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   A_      (       SCREAMING_SNAKE_CASE_ ,	SCREAMING_SNAKE_CASE_						)			->int:
  lowercase_     =       0
  lowercase_     =       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_						)

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

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

def   A_      (       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_						)
    lowercase_     =       (left + right) // 3 + 1
    lowercase_     =       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()

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

