






def 		SCREAMING_SNAKE_CASE							( __lowerCAmelCase      )			->     str:
     UpperCamelCase__      :       Dict	    =  0

     # if input_string is "aba" than new_input_string become "a|b|a"
     UpperCamelCase__      :       List[Any]	    =  ""
     UpperCamelCase__      :       str	    =  ""

     # append each character + "|" in new_string for range(0, length-1)
     for i in input_string[: len(__lowerCAmelCase      ) - 1]:
          new_input_string += i + "|"
     # append last character
     new_input_string += input_string[-1]

     # we will store the starting and ending of previous furthest ending palindromic
     # substring
     UpperCamelCase__    ,					UpperCamelCase__      :       Tuple	    =  0, 0

     # length[i] shows the length of palindromic substring with center i
     UpperCamelCase__      :       Union[str, Any]	    =  [1 for i in range(len(__lowerCAmelCase      )      )]

     # for each character in new_string find corresponding palindromic string
     UpperCamelCase__      :       Any	    =  0
     for j in range(len(__lowerCAmelCase      )      ):
          UpperCamelCase__      :       Union[str, Any]	    =  1 if j > r else min(length[l + r - j] // 2 ,   r - j + 1      )
          while (
              j - k >= 0
              and j + k < len(__lowerCAmelCase      )
              and new_input_string[k + j] == new_input_string[j - k]
          ):
               k += 1

          UpperCamelCase__      :       Optional[Any]	    =  2 * k - 1

          # does this string is ending after the previously explored end (that is r) ?
          # if yes the update the new r to the last index of this
          if j + k - 1 > r:
               UpperCamelCase__      :       Optional[int]	    =  j - k + 1  # noqa: E741
               UpperCamelCase__      :       Tuple	    =  j + k - 1

          # update max_length and start position
          if max_length < length[j]:
               UpperCamelCase__      :       Tuple	    =  length[j]
               UpperCamelCase__      :       Union[str, Any]	    =  j

    # create that string
     UpperCamelCase__      :       Optional[int]	    =  new_input_string[start - max_length // 2 : start + max_length // 2 + 1]
     for i in s:
          if i != "|":
               output_string += i

     return output_string


if __name__ == "__main__":
 import doctest

 doctest.testmod()







from __future__ import annotations







def 		SCREAMING_SNAKE_CASE							( __lowerCAmelCase ,   __lowerCAmelCase      )			->     bool:
     if len(__lowerCAmelCase      ) == 0:
          return False
     UpperCamelCase__      :       Any	    =  len(__lowerCAmelCase      ) // 2
     if a_list[midpoint] == item:
          return True
     if item < a_list[midpoint]:
          return binary_search(a_list[:midpoint] ,   __lowerCAmelCase      )
     else:
          return binary_search(a_list[midpoint + 1 :] ,   __lowerCAmelCase      )


if __name__ == "__main__":
 lowerCamelCase     :							Any    =input('''Enter numbers separated by comma:\n''').strip()
 lowerCamelCase     :							Dict    =[int(item.strip()) for item in user_input.split(''',''')]
 lowerCamelCase     :							List[str]    =int(input('''Enter the number to be found in the list:\n''').strip())
 lowerCamelCase     :							Union[str, Any]    ='''''' if binary_search(sequence, target) else '''not '''
 print(F"""{target} was {not_str}found in {sequence}""")