
from __future__ import annotations




def 	A_ (							snake_case							:   List[str] ,      snake_case							:   List[Any] ,      snake_case							:   Tuple ,      snake_case							:   Tuple )      ->    Optional[int]:  # noqa: E741



						'''simple docstring'''

						while r - l > 1:
												__UpperCamelCase       =			(l + r) // 2
												if v[m] >= key:
																		__UpperCamelCase       =			m
												else:
																		__UpperCamelCase       =			m  # noqa: E741
						return r




def 	A_ (							snake_case							:   list[int] )      ->    int:



						'''simple docstring'''

						if len(snake_case ) == 0:
												return 0

						__UpperCamelCase       =			[0] * len(snake_case )
						__UpperCamelCase       =			1

						__UpperCamelCase       =			v[0]

						for i in range(1 ,      len(snake_case ) ):
												if v[i] < tail[0]:
																		__UpperCamelCase       =			v[i]
												elif v[i] > tail[length - 1]:
																		__UpperCamelCase       =			v[i]
																		length += 1
												else:
																		__UpperCamelCase       =			v[i]

						return length


if __name__ == "__main__":
				import doctest

				doctest.testmod()






from collections import Counter
from timeit import timeit




def 	A_ (							snake_case							:   str = "" ,      )      ->    bool:



						'''simple docstring'''

						return sum(c % 2 for c in Counter(input_str.replace(''' ''' ,      '''''' ).lower() ).values() ) < 2




def 	A_ (							snake_case							:   str = "" )      ->    bool:



						'''simple docstring'''

						if len(snake_case ) == 0:
												return True
						__UpperCamelCase       =			input_str.replace(''' ''' ,      '''''' ).lower()
						# character_freq_dict: Stores the frequency of every character in the input string
						__UpperCamelCase       =			{}

						for character in lower_case_input_str:
												__UpperCamelCase       =			character_freq_dict.get(snake_case ,      0 ) + 1
						__UpperCamelCase       =			0

						for character_count in character_freq_dict.values():
												if character_count % 2:
																		odd_char += 1
						if odd_char > 1:
												return False
						return True




def 	A_ (							snake_case							:   str = "" )      ->    None:



						'''simple docstring'''

						print('''\nFor string = ''' ,      snake_case ,      ''':''' )
						print(
						    '''> can_string_be_rearranged_as_palindrome_counter()''' ,      '''\tans =''' ,      can_string_be_rearranged_as_palindrome_counter(snake_case ) ,      '''\ttime =''' ,      timeit(
						        '''z.can_string_be_rearranged_as_palindrome_counter(z.check_str)''' ,      setup='''import __main__ as z''' ,      ) ,      '''seconds''' ,      )
						print(
						    '''> can_string_be_rearranged_as_palindrome()''' ,      '''\tans =''' ,      can_string_be_rearranged_as_palindrome(snake_case ) ,      '''\ttime =''' ,      timeit(
						        '''z.can_string_be_rearranged_as_palindrome(z.check_str)''' ,      setup='''import __main__ as z''' ,      ) ,      '''seconds''' ,      )


if __name__ == "__main__":
				lowercase__							:							Tuple									=			input(
				    "Enter string to determine if it can be rearranged as a palindrome or not: "
				).strip()
				benchmark(check_str)
				lowercase__							:							Dict									=			can_string_be_rearranged_as_palindrome_counter(check_str)
				print(F"{check_str} can {'' if status else 'not '}be rearranged as a palindrome")




