




'''simple docstring'''





from __future__ import annotations

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

SCREAMING_SNAKE_CASE:    Optional[int]											=   TypeVar('''T''')
SCREAMING_SNAKE_CASE:    List[Any]											=   TypeVar('''U''')



class       lowercase_		(Generic[T, U]   ):



						def __init__( self  :      Optional[Any]				,       snake_case__  :      Optional[int]				,       snake_case__  :      Optional[Any]     ):

								"""simple docstring"""

								SCREAMING_SNAKE_CASE_							=       key
								SCREAMING_SNAKE_CASE_							=       val
								SCREAMING_SNAKE_CASE_							=       0
								SCREAMING_SNAKE_CASE_							=       None
								SCREAMING_SNAKE_CASE_							=       None






						def __repr__( self  :      Any     ):

								"""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       lowercase_		(Generic[T, U]   ):



						def __init__( self  :      int     ):

								"""simple docstring"""

								SCREAMING_SNAKE_CASE_							=       DoubleLinkedListNode(a_				,       a_     )
								SCREAMING_SNAKE_CASE_							=       DoubleLinkedListNode(a_				,       a_     )
								SCREAMING_SNAKE_CASE_			,							SCREAMING_SNAKE_CASE_							=       self.rear, self.head



						def __repr__( self  :      Any     ):

								"""simple docstring"""

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



						def   __a				( self  :      str				,       snake_case__  :      Any     ):

								"""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
								node.freq += 1
								self._position_node(a_     )



						def   __a				( self  :      Any				,       snake_case__  :      Tuple     ):

								"""simple docstring"""

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

										SCREAMING_SNAKE_CASE_							=       previous_node.prev
										SCREAMING_SNAKE_CASE_							=       node.prev
										SCREAMING_SNAKE_CASE_							=       previous_node
										SCREAMING_SNAKE_CASE_							=       node






						def   __a				( self  :      Any				,       snake_case__  :      List[str]     ):

								"""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       lowercase_		(Generic[T, U]   ):
						lowerCAmelCase__ 			={}



						def __init__( self  :      int				,       snake_case__  :      Optional[int]     ):

								"""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  :      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  :      Tuple				,       snake_case__  :      Dict     ):

								"""simple docstring"""

								return key in self.cache



						def   __a				( self  :      str				,       snake_case__  :      int     ):

								"""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(a_     )
										return node.val
								self.miss += 1
								return None



						def   __a				( self  :      Optional[int]				,       snake_case__  :      str				,       snake_case__  :      Tuple     ):

								"""simple docstring"""

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

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

								else:
										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(a_     )






						@classmethod
						def   __a				( cls  :      List[Any]				,       snake_case__  :      Tuple = 1_28     ):

								"""simple docstring"""

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

												SCREAMING_SNAKE_CASE_							=       cls.decorator_function_to_instance_map[func].get(args[0]     )
												if result is None:
														SCREAMING_SNAKE_CASE_							=       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()





from __future__ import annotations


def 				_a       (				lowerCAmelCase						,	lowerCAmelCase   )->  int:
		SCREAMING_SNAKE_CASE_			,							SCREAMING_SNAKE_CASE_							=       0, len(lowerCAmelCase   ) - 1
		while start_ind <= end_ind:
				if array[start_ind] == search_item:
						return start_ind
				elif array[end_ind] == search_item:
						return end_ind
				else:
						start_ind += 1
						end_ind -= 1
    # returns -1 if search_item is not found in array
		return -1


if __name__ == "__main__":
						print(double_linear_search(list(range(1_0_0)), 4_0))