





from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

SCREAMING_SNAKE_CASE_						   =       TypeVar("""T""")
SCREAMING_SNAKE_CASE_						   =       TypeVar("""U""")

class 		UpperCamelCase__ (      Generic[T, U]   ):



     '''simple docstring'''

     def __init__(							self						:    str						,lowerCamelCase__						:    Union[str, Any]						,lowerCamelCase__						:    Dict       )     ->		Optional[Any]:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						key
           SCREAMING_SNAKE_CASE		=						val
           SCREAMING_SNAKE_CASE		=						None
           SCREAMING_SNAKE_CASE		=						None






     def __repr__(							self						:    Dict       )     ->		List[str]:




           '''simple docstring'''


           return (
               F"""Node: key: {self.key}, val: {self.val}, """
               F"""has next: {bool(self.next       )}, has prev: {bool(self.prev       )}"""
           )

class 		UpperCamelCase__ (      Generic[T, U]   ):



     '''simple docstring'''

     def __init__(							self						:    int       )     ->		Optional[Any]:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						DoubleLinkedListNode(UpperCamelCase__						,UpperCamelCase__       )
           SCREAMING_SNAKE_CASE		=						DoubleLinkedListNode(UpperCamelCase__						,UpperCamelCase__       )
           SCREAMING_SNAKE_CASE,					SCREAMING_SNAKE_CASE		=						self.rear, self.head






     def __repr__(							self						:    Dict       )     ->		Optional[Any]:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						["""DoubleLinkedList"""]
           SCREAMING_SNAKE_CASE		=						self.head
           while node.next is not None:
                 rep.append(str(UpperCamelCase__       )       )
                 SCREAMING_SNAKE_CASE		=						node.next
           rep.append(str(self.rear       )       )
           return ",\n    ".join(UpperCamelCase__       )






     def 				SCREAMING_SNAKE_CASE__  (							self						:    Union[str, Any]						,lowerCamelCase__						:    List[str]       )     ->		Tuple:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						self.rear.prev

           # All nodes other than self.head are guaranteed to have non-None previous
           assert previous is not None

           SCREAMING_SNAKE_CASE		=						node
           SCREAMING_SNAKE_CASE		=						previous
           SCREAMING_SNAKE_CASE		=						node
           SCREAMING_SNAKE_CASE		=						self.rear






     def 				SCREAMING_SNAKE_CASE__  (							self						:    int						,lowerCamelCase__						:    Union[str, Any]       )     ->		int:




           '''simple docstring'''


           if node.prev is None or node.next is None:
                 return None

           SCREAMING_SNAKE_CASE		=						node.next
           SCREAMING_SNAKE_CASE		=						node.prev
           SCREAMING_SNAKE_CASE		=						None
           SCREAMING_SNAKE_CASE		=						None
           return node

class 		UpperCamelCase__ (      Generic[T, U]   ):



     '''simple docstring'''

     __snake_case    :	List[Any]			=			{}






     def __init__(							self						:    Optional[int]						,lowerCamelCase__						:    Optional[Any]       )     ->		Dict:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						DoubleLinkedList()
           SCREAMING_SNAKE_CASE		=						capacity
           SCREAMING_SNAKE_CASE		=						0
           SCREAMING_SNAKE_CASE		=						0
           SCREAMING_SNAKE_CASE		=						0
           SCREAMING_SNAKE_CASE		=						{}






     def __repr__(							self						:    List[Any]       )     ->		Optional[int]:




           '''simple docstring'''


           return (
               F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
               F"""capacity={self.capacity}, current size={self.num_keys})"""
           )






     def __contains__(							self						:    Optional[int]						,lowerCamelCase__						:    Dict       )     ->		Tuple:




           '''simple docstring'''


           return key in self.cache






     def 				SCREAMING_SNAKE_CASE__  (							self						:    str						,lowerCamelCase__						:    int       )     ->		Optional[Any]:




           '''simple docstring'''


           if key in self.cache:
                 self.hits += 1
                 SCREAMING_SNAKE_CASE		=						self.cache[key]
                 SCREAMING_SNAKE_CASE		=						self.list.remove(self.cache[key]       )
                 assert node == value_node

                 # node is guaranteed not None because it is in self.cache
                 assert node is not None
                 self.list.add(UpperCamelCase__       )
                 return node.val
           self.miss += 1
           return None






     def 				SCREAMING_SNAKE_CASE__  (							self						:    str						,lowerCamelCase__						:    Optional[int]						,lowerCamelCase__						:    Optional[int]       )     ->		Optional[Any]:




           '''simple docstring'''


           if key not in self.cache:
                 if self.num_keys >= self.capacity:
                       # delete first node (oldest) when over capacity
                       SCREAMING_SNAKE_CASE		=						self.list.head.next

                       # guaranteed to have a non-None first node when num_keys > 0
                       # explain to type checker via assertions
                       assert first_node is not None
                       assert first_node.key is not None
                       assert (
                           self.list.remove(UpperCamelCase__       ) is not None
                       )  # node guaranteed to be in list assert node.key is not None

                       del self.cache[first_node.key]
                       self.num_keys -= 1
                 SCREAMING_SNAKE_CASE		=						DoubleLinkedListNode(UpperCamelCase__						,UpperCamelCase__       )
                 self.list.add(self.cache[key]       )
                 self.num_keys += 1

           else:
                 # bump node to the end of the list, update value
                 SCREAMING_SNAKE_CASE		=						self.list.remove(self.cache[key]       )
                 assert node is not None  # node guaranteed to be in list
                 SCREAMING_SNAKE_CASE		=						value
                 self.list.add(UpperCamelCase__       )






     @classmethod
     def 				SCREAMING_SNAKE_CASE__  (							cls						:    str						,lowerCamelCase__						:    Tuple = 128       )     ->		Union[str, Any]:




           '''simple docstring'''


           def cache_decorator_inner(lowerCamelCase__						:    List[str]       ) -> Callable[..., U]:
                 def cache_decorator_wrapper(*lowerCamelCase__						:    Optional[int]       ) -> U:
                       if func not in cls.decorator_function_to_instance_map:
                             SCREAMING_SNAKE_CASE		=						LRUCache(UpperCamelCase__       )

                       SCREAMING_SNAKE_CASE		=						cls.decorator_function_to_instance_map[func].get(args[0]       )
                       if result is None:
                             SCREAMING_SNAKE_CASE		=						func(*UpperCamelCase__       )
                             cls.decorator_function_to_instance_map[func].put(args[0]						,UpperCamelCase__       )
                       return result

                 def cache_info() -> LRUCache[T, U]:
                       return cls.decorator_function_to_instance_map[func]

                 setattr(UpperCamelCase__						,"""cache_info"""						,UpperCamelCase__       )  # noqa: B010

                 return cache_decorator_wrapper

           return cache_decorator_inner


if __name__ == "__main__":
      import doctest

      doctest.testmod()








def __UpperCamelCase			(       _A  ):
						if not numbers:
												return 0

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

						lowerCAmelCase_      			=  lowerCAmelCase_      			=  lowerCAmelCase_      			=  numbers[0]

						for i in range(1 ,  len(_A  )  ):
												# update the maximum and minimum subarray products
												lowerCAmelCase_      			=  numbers[i]
												if number < 0:
																		lowerCAmelCase_			,					lowerCAmelCase_      			=  min_till_now, max_till_now
												lowerCAmelCase_      			=  max(_A ,  max_till_now * number  )
												lowerCAmelCase_      			=  min(_A ,  min_till_now * number  )

												# update the maximum product found till now
												lowerCAmelCase_      			=  max(_A ,  _A  )

						return max_prod




