





from __future__ import annotations

from random import choice






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:Tuple   )      ->   Dict:
 return choice(SCREAMING_SNAKE_CASE   )






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:list[int]   ,   SCREAMING_SNAKE_CASE		:int   )      ->   int:
 __lowerCAmelCase					:	Union[str, Any]      =       random_pivot(SCREAMING_SNAKE_CASE   )

 # partition based on pivot
 # linear time
 __lowerCAmelCase					:	Any      =       [e for e in lst if e < pivot]
 __lowerCAmelCase					:	str      =       [e for e in lst if e > pivot]

 # if we get lucky, pivot might be the element we want.
 # we can easily see this:
 # small (elements smaller than k)
 # + pivot (kth element)
 # + big (elements larger than k)
 if len(SCREAMING_SNAKE_CASE   ) == k - 1:
  return pivot
 # pivot is in elements bigger than k
 elif len(SCREAMING_SNAKE_CASE   ) < k - 1:
  return kth_number(SCREAMING_SNAKE_CASE   ,   k - len(SCREAMING_SNAKE_CASE   ) - 1   )
 # pivot is in elements smaller than k
 else:
  return kth_number(SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   )


if __name__ == "__main__":
      import doctest

      doctest.testmod()






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:list[int]   )      ->   int:
 if not numbers:
  return 0

 if not isinstance(SCREAMING_SNAKE_CASE   ,   (list, tuple)   ) or not all(
     isinstance(SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   ) for number in numbers   ):
  raise ValueError("""numbers must be an iterable of integers"""   )

 __lowerCAmelCase					:	int      =       numbers[0]

 for i in range(1   ,   len(SCREAMING_SNAKE_CASE   )   ):
  # update the maximum and minimum subarray products
  __lowerCAmelCase					:	List[str]      =       numbers[i]
  if number < 0:
   __lowerCAmelCase ,					__lowerCAmelCase					:	Union[str, Any]      =       min_till_now, max_till_now
  __lowerCAmelCase					:	Optional[int]      =       max(SCREAMING_SNAKE_CASE   ,   max_till_now * number   )
  __lowerCAmelCase					:	List[Any]      =       min(SCREAMING_SNAKE_CASE   ,   min_till_now * number   )

  # update the maximum product found till now
  __lowerCAmelCase					:	List[str]      =       max(SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   )

 return max_prod