
"""simple docstring"""
from __future__ import annotations

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

__magic_name__		       =				TypeVar('''T''')
__magic_name__		       =				TypeVar('''U''')


class    _lowerCAmelCase						(						Generic[T, U]						):



							def __init__(      self ,						a_ ,						a_   )							->							Any:
								_UpperCAmelCase =						key
								_UpperCAmelCase =						val
								_UpperCAmelCase =						0
								_UpperCAmelCase =						None
								_UpperCAmelCase =						None



							def __repr__(      self   )							->							str:
								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   )							->							None:
								_UpperCAmelCase =						DoubleLinkedListNode(a_ ,						a_   )
								_UpperCAmelCase =						DoubleLinkedListNode(a_ ,						a_   )
								_UpperCAmelCase ,      _UpperCAmelCase =						self.rear, self.head



							def __repr__(      self   )							->							str:
								_UpperCAmelCase =						["DoubleLinkedList"]
								_UpperCAmelCase =						self.head
								while node.next is not None:
									rep.append(str(a_   )   )
									_UpperCAmelCase =						node.next
								rep.append(str(self.rear   )   )
								return ",\n    ".join(a_   )



							def       _a   (      self ,						a_   )							->							None:
								_UpperCAmelCase =						self.rear.prev

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

								_UpperCAmelCase =						node
								_UpperCAmelCase =						previous
								_UpperCAmelCase =						node
								_UpperCAmelCase =						self.rear
								node.freq += 1
								self._position_node(a_   )



							def       _a   (      self ,						a_   )							->							None:

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

									_UpperCAmelCase =						previous_node.prev
									_UpperCAmelCase =						node.prev
									_UpperCAmelCase =						previous_node
									_UpperCAmelCase =						node



							def       _a   (      self ,						a_   )							->							DoubleLinkedListNode[T, U] | None:

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

								_UpperCAmelCase =						node.next
								_UpperCAmelCase =						node.prev
								_UpperCAmelCase =						None
								_UpperCAmelCase =						None
								return node





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



							def __init__(      self ,						a_   )							->							List[Any]:
								_UpperCAmelCase =						DoubleLinkedList()
								_UpperCAmelCase =						capacity
								_UpperCAmelCase =						0
								_UpperCAmelCase =						0
								_UpperCAmelCase =						0
								_UpperCAmelCase =						{}



							def __repr__(      self   )							->							str:
								return (
								    f"CacheInfo(hits={self.hits}, misses={self.miss}, "
								    f"capacity={self.capacity}, current_size={self.num_keys})"
								)



							def __contains__(      self ,						a_   )							->							bool:
								return key in self.cache



							def       _a   (      self ,						a_   )							->							U | None:

								if key in self.cache:
									self.hits += 1
									_UpperCAmelCase =						self.cache[key]
									_UpperCAmelCase =						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       _a   (      self ,						a_ ,						a_   )							->							None:

								if key not in self.cache:
									if self.num_keys >= self.capacity:
										# delete first node when over capacity
										_UpperCAmelCase =						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
									_UpperCAmelCase =						DoubleLinkedListNode(a_ ,						a_   )
									self.list.add(self.cache[key]   )
									self.num_keys += 1

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



							@classmethod
							def       _a   (      cls ,						a_ = 128   )							->							Callable[[Callable[[T], U]], Callable[..., U]]:

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

										_UpperCAmelCase =						cls.decorator_function_to_instance_map[func].get(args[0]   )
										if result is None:
											_UpperCAmelCase =						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"""
def     __lowerCamelCase  (		UpperCamelCase__ = 400_0000      ):


	"""simple docstring"""






	_UpperCAmelCase =						1
	_UpperCAmelCase =						2
	_UpperCAmelCase =						0
	while j <= n:
		if j % 2 == 0:
			total += j
		_UpperCAmelCase ,      _UpperCAmelCase =						j, i + j

	return total


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




