

"""simple docstring"""






from __future__ import annotations

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

__lowerCAmelCase				      =   TypeVar('''T''')
__lowerCAmelCase				      =   TypeVar('''U''')
class 	_lowerCAmelCase    (      Generic[T, U]       ):

							def __init__( self       :    str ,		a       :    T | None ,		a       :    U | None    )   ->    List[Any]:

									"""simple docstring"""
									lowercase										=							key
									lowercase										=							val
									lowercase										=							0
									lowercase										=							None
									lowercase										=							None

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

									"""simple docstring"""
									return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
									    self.key ,		self.val ,		self.freq ,		self.next is not None ,		self.prev is not None    )




class 	_lowerCAmelCase    (      Generic[T, U]       ):

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

									"""simple docstring"""
									lowercase										=							DoubleLinkedListNode(a ,		a    )
									lowercase										=							DoubleLinkedListNode(a ,		a    )
									lowercase					,  lowercase										=							self.rear, self.head

							def __repr__( self       :    str    )   ->    str:

									"""simple docstring"""
									lowercase										=							['''DoubleLinkedList''']
									lowercase										=							self.head
									while node.next is not None:
											rep.append(str(a    )    )
											lowercase										=							node.next
									rep.append(str(self.rear    )    )
									return ",\n    ".join(a    )

							def 					_lowerCAmelCase  ( self       :    Optional[int] ,		a       :    DoubleLinkedListNode[T, U]    )   ->    None:

									"""simple docstring"""
									lowercase										=							self.rear.prev

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

									lowercase										=							node
									lowercase										=							previous
									lowercase										=							node
									lowercase										=							self.rear
									node.freq += 1
									self._position_node(a    )

							def 					_lowerCAmelCase  ( self       :    Union[str, Any] ,		a       :    DoubleLinkedListNode[T, U]    )   ->    None:

									"""simple docstring"""







									while node.prev is not None and node.prev.freq > node.freq:
											# swap node with previous node
											lowercase										=							node.prev

											lowercase										=							previous_node.prev
											lowercase										=							node.prev
											lowercase										=							previous_node
											lowercase										=							node

							def 					_lowerCAmelCase  ( self       :    Tuple ,		a       :    DoubleLinkedListNode[T, U]    )   ->    DoubleLinkedListNode[T, U] | None:

									"""simple docstring"""







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

									lowercase										=							node.next
									lowercase										=							node.prev
									lowercase										=							None
									lowercase										=							None
									return node




class 	_lowerCAmelCase    (      Generic[T, U]       ):
							__lowerCAmelCase					:    dict[Callable[[T], U], LFUCache[T, U]]     =  {}

							def __init__( self       :    Dict ,		a       :    int    )   ->    Union[str, Any]:

									"""simple docstring"""
									lowercase										=							DoubleLinkedList()
									lowercase										=							capacity
									lowercase										=							0
									lowercase										=							0
									lowercase										=							0
									lowercase										=							{}

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

									"""simple docstring"""
									return (
									    f"""CacheInfo(hits={self.hits}, misses={self.miss}, """
									    f"""capacity={self.capacity}, current_size={self.num_keys})"""
									)

							def __contains__( self       :    Any ,		a       :    T    )   ->    bool:

									"""simple docstring"""
									return key in self.cache

							def 					_lowerCAmelCase  ( self       :    str ,		a       :    T    )   ->    U | None:

									"""simple docstring"""







									if key in self.cache:
											self.hits += 1
											lowercase										=							self.cache[key]
											lowercase										=							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(a    )
											return node.val
									self.miss += 1
									return None

							def 					_lowerCAmelCase  ( self       :    Any ,		a       :    T ,		a       :    U    )   ->    None:

									"""simple docstring"""







									if key not in self.cache:
											if self.num_keys >= self.capacity:
													# delete first node when over capacity
													lowercase										=							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(a    ) is not None
													# first_node guaranteed to be in list

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

									else:
											lowercase										=							self.list.remove(self.cache[key]    )
											assert node is not None  # node guaranteed to be in list
											lowercase										=							value
											self.list.add(a    )

							@classmethod
							def 					_lowerCAmelCase  ( cls       :    type[LFUCache[T, U]] ,		a       :    int = 128    )   ->    Callable[[Callable[[T], U]], Callable[..., U]]:

									"""simple docstring"""







									def cache_decorator_inner(a       :    Callable[[T], U]    ) -> Callable[..., U]:
											def cache_decorator_wrapper(*a       :    T    ) -> U:
													if func not in cls.decorator_function_to_instance_map:
															lowercase										=							LFUCache(a    )

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

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

											setattr(a ,		'''cache_info''' ,		a    )  # noqa: B010

											return cache_decorator_wrapper

									return cache_decorator_inner


if __name__ == "__main__":
							import doctest

							doctest.testmod()







'''simple docstring'''


from itertools import combinations_with_replacement







def 						__magic_name__(			_A = 100       ):
						'''simple docstring'''





						UpperCamelCase__       =			[*list(range(1    ,   21       )       ), 25]
						UpperCamelCase__       =			[2 * x for x in range(1    ,   21       )] + [50]
						UpperCamelCase__       =			[3 * x for x in range(1    ,   21       )]
						UpperCamelCase__       =			singles + doubles + triples + [0]

						UpperCamelCase__       =			0
						UpperCamelCase__       =			42
						UpperCamelCase__       =			42
						UpperCamelCase__       =			42
						UpperCamelCase__       =			42

						for double in doubles:
												for throwa, throwa in combinations_with_replacement(_A    ,   2       ):
																		UpperCamelCase__       =			double + throwa + throwa
																		if checkout_total < limit:
																								num_checkouts += 1

						return num_checkouts


if __name__ == "__main__":
					print(f"""{solution() = }""")
