


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.
UpperCAmelCase_   :				Tuple						      = 10







def  SCREAMING_SNAKE_CASE_		(    __A				:    int						,					__A				:    int						,					__A				:    list[int]						,					__A				:    int       )			->	int:

       """simple docstring"""

       for i in range(__A						,					__A       ):
              if array[i] == target:
                     return i
       return -1







def  SCREAMING_SNAKE_CASE_		(    __A				:    list[int]						,					__A				:    int       )			->	int:

       """simple docstring"""

       a_      :	Any							=						0
       a_      :	Union[str, Any]							=						len(__A       )
       while left <= right:
              if right - left < precision:
                     return lin_search(__A						,					__A						,					__A						,					__A       )

              a_      :	List[str]							=						(left + right) // 3 + 1
              a_      :	Optional[int]							=						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]:
                     a_      :	Dict							=						one_third - 1
              elif array[two_third] < target:
                     a_      :	Optional[int]							=						two_third + 1

              else:
                     a_      :	Any							=						one_third + 1
                     a_      :	List[str]							=						two_third - 1
       else:
              return -1







def  SCREAMING_SNAKE_CASE_		(    __A				:    int						,					__A				:    int						,					__A				:    list[int]						,					__A				:    int       )			->	int:

       """simple docstring"""

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


if __name__ == "__main__":
   import doctest

   doctest.testmod()

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






def  SCREAMING_SNAKE_CASE_		(    __A				:    list       )			->	list:

       """simple docstring"""

       if len(__A       ) <= 1:
              return [tuple(__A       )]

       a_      :	Optional[Any]							=						[]

       def generate(__A				:    int						,					__A				:    list       ):
              a_      :	str							=						[0] * n
              res.append(tuple(__A       )       )

              a_      :	Optional[int]							=						0
              while i < n:
                     if c[i] < i:
                            if i % 2 == 0:
                                   a_							,	a_      :	Dict							=						arr[i], arr[0]
                            else:
                                   a_							,	a_      :	Union[str, Any]							=						arr[i], arr[c[i]]
                            res.append(tuple(__A       )       )
                            c[i] += 1
                            a_      :	Dict							=						0
                     else:
                            a_      :	Optional[Any]							=						0
                            i += 1

       generate(len(__A       )						,					__A       )
       return res


if __name__ == "__main__":
   UpperCAmelCase_   :				Union[str, Any]						      = input('Enter numbers separated by a comma:\n').strip()
   UpperCAmelCase_   :				Optional[Any]						      = [int(item) for item in user_input.split(',')]
   print(heaps(arr))


