'''simple docstring'''




from __future__ import annotations

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

__SCREAMING_SNAKE_CASE       :     List[str]     =  TypeVar("""T""")
__SCREAMING_SNAKE_CASE       :     str     =  TypeVar("""U""")

class 	lowerCamelCase_	(Generic[T, U]    ):
      '''simple docstring'''

      def __init__(       self						:				Optional[int]						,					A						:				T | None						,					A						:				U | None       ):
             _UpperCAmelCase     :  Any							      =    key
             _UpperCAmelCase     :  List[str]							      =    val
             _UpperCAmelCase     :  DoubleLinkedListNode[T, U] | None							      =    None
             _UpperCAmelCase     :  DoubleLinkedListNode[T, U] | None							      =    None





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

class 	lowerCamelCase_	(Generic[T, U]    ):
      '''simple docstring'''

      def __init__(       self						:				Any       ):
             _UpperCAmelCase     :  DoubleLinkedListNode[T, U]							      =    DoubleLinkedListNode(A						,					A       )
             _UpperCAmelCase     :  DoubleLinkedListNode[T, U]							      =    DoubleLinkedListNode(A						,					A       )
             _UpperCAmelCase      ,  _UpperCAmelCase     :  Dict							      =    self.rear, self.head




      def __repr__(       self						:				Optional[int]       ):
             _UpperCAmelCase     :  List[str]							      =    ["DoubleLinkedList"]
             _UpperCAmelCase     :  Tuple							      =    self.head
             while node.next is not None:
                    rep.append(str(A       )       )
                    _UpperCAmelCase     :  str							      =    node.next
             rep.append(str(self.rear       )       )
             return ",\n    ".join(A       )




      def      _A	(       self						:				Union[str, Any]						,					A						:				DoubleLinkedListNode[T, U]       ):
             _UpperCAmelCase     :  Optional[Any]							      =    self.rear.prev

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

             _UpperCAmelCase     :  Dict							      =    node
             _UpperCAmelCase     :  List[Any]							      =    previous
             _UpperCAmelCase     :  Optional[int]							      =    node
             _UpperCAmelCase     :  str							      =    self.rear





      def      _A	(       self						:				List[Any]						,					A						:				DoubleLinkedListNode[T, U]       ):

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

             _UpperCAmelCase     :  str							      =    node.next
             _UpperCAmelCase     :  List[Any]							      =    node.prev
             _UpperCAmelCase     :  Tuple							      =    None
             _UpperCAmelCase     :  List[str]							      =    None
             return node

class 	lowerCamelCase_	(Generic[T, U]    ):
      '''simple docstring'''

      __UpperCamelCase:  dict[Callable[[T], U], LRUCache[T, U]]						=						{}




      def __init__(       self						:				Dict						,					A						:				int       ):
             _UpperCAmelCase     :  DoubleLinkedList[T, U]							      =    DoubleLinkedList()
             _UpperCAmelCase     :  int							      =    capacity
             _UpperCAmelCase     :  Tuple							      =    0
             _UpperCAmelCase     :  Any							      =    0
             _UpperCAmelCase     :  str							      =    0
             _UpperCAmelCase     :  dict[T, DoubleLinkedListNode[T, U]]							      =    {}




      def __repr__(       self						:				List[Any]       ):
             return (
                 F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
                 F"""capacity={self.capacity}, current size={self.num_keys})"""
             )




      def __contains__(       self						:				Optional[Any]						,					A						:				T       ):
             return key in self.cache




      def      _A	(       self						:				int						,					A						:				T       ):
             # Note: pythonic interface would throw KeyError rather than return None

             if key in self.cache:
                    self.hits += 1
                    _UpperCAmelCase     :  DoubleLinkedListNode[T, U]							      =    self.cache[key]
                    _UpperCAmelCase     :  Optional[int]							      =    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						:				List[str]						,					A						:				T						,					A						:				U       ):

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

                           del self.cache[first_node.key]
                           self.num_keys -= 1
                    _UpperCAmelCase     :  List[str]							      =    DoubleLinkedListNode(A						,					A       )
                    self.list.add(self.cache[key]       )
                    self.num_keys += 1

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





      @classmethod
      def      _A	(       cls						:				Optional[int]						,					A						:				int = 128       ):

             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:
                                  _UpperCAmelCase     :  Tuple							      =    LRUCache(A       )

                           _UpperCAmelCase     :  List[str]							      =    cls.decorator_function_to_instance_map[func].get(args[0]       )
                           if result is None:
                                  _UpperCAmelCase     :  List[Any]							      =    func(*A       )
                                  cls.decorator_function_to_instance_map[func].put(args[0]						,					A       )
                           return result

                    def cache_info() -> LRUCache[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 	UpperCamelCase_							(					_UpperCAmelCase  :      list    )    ->    list:


       """simple docstring"""







       _UpperCAmelCase     :  List[Any]							      =    len(_UpperCAmelCase    )
       for _ in range(_UpperCAmelCase    ):
              for i in range(_ % 2			,	arr_size - 1			,	2    ):
                     if arr[i + 1] < arr[i]:
                            _UpperCAmelCase      ,  _UpperCAmelCase     :  int							      =    arr[i + 1], arr[i]

       return arr


if __name__ == "__main__":
  __SCREAMING_SNAKE_CASE       :     Optional[Any]     =  list(range(10, 0, -1))
  print(F'Original: {arr}. Sorted: {odd_even_transposition(arr)}')

