code: 
  
  
  """simple docstring"""
  class   lowercase__							:
  
  
  
  
  
  			def __init__(       self)     ->     None:
  						# numbermap keys are the number and its values are lists of indexes sorted
  						# in ascending order
  						_lowerCamelCase  :				List[str]      =		{}
  						# indexmap keys are an index and it's values are the number at that index
  						_lowerCamelCase  :				List[str]      =		{}
  
  
  
  
  
  			def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)     ->     list[int]:
  						if isinstance(__A			,      (range, str)):
  									_lowerCamelCase  :				List[str]      =		list(__A)
  						elif not isinstance(__A			,      __A):
  									raise TypeError(
  									    """binary_search_delete() only accepts either a list, range or str""")
  
  						_lowerCamelCase  :				Dict      =		0
  						_lowerCamelCase  :				List[Any]      =		len(__A) - 1
  
  						while low <= high:
  									_lowerCamelCase  :				Union[str, Any]      =		(low + high) // 2
  									if array[mid] == item:
  												array.pop(__A)
  												return array
  									elif array[mid] < item:
  												_lowerCamelCase  :				Tuple      =		mid + 1
  									else:
  												_lowerCamelCase  :				Optional[int]      =		mid - 1
  						raise ValueError(
  						    """Either the item is not in the array or the array was unsorted""")
  
  
  
  
  
  			def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)     ->     list[int]:
  						if isinstance(__A			,      (range, str)):
  									_lowerCamelCase  :				Dict      =		list(__A)
  						elif not isinstance(__A			,      __A):
  									raise TypeError(
  									    """binary_search_insert() only accepts either a list, range or str""")
  
  						_lowerCamelCase  :				Optional[int]      =		0
  						_lowerCamelCase  :				List[str]      =		len(__A) - 1
  
  						while low <= high:
  									_lowerCamelCase  :				Optional[Any]      =		(low + high) // 2
  									if array[mid] == index:
  												# If the item already exists in the array,
  												# insert it after the existing item
  												array.insert(mid + 1			,      __A)
  												return array
  									elif array[mid] < index:
  												_lowerCamelCase  :				Optional[Any]      =		mid + 1
  									else:
  												_lowerCamelCase  :				List[str]      =		mid - 1
  
          # If the item doesn't exist in the array, insert it at the appropriate position
  						array.insert(__A			,      __A)
  						return array
  
  
  
  
  
  			def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)     ->     None:
  						# Remove previous index
  						if index in self.indexmap:
  									_lowerCamelCase  :				Tuple      =		self.indexmap[index]
  									if len(self.numbermap[n]) == 1:
  												del self.numbermap[n]
  									else:
  												_lowerCamelCase  :				List[str]      =		self.binary_search_delete(self.numbermap[n]			,      __A)
  
          # Set new index
  						_lowerCamelCase  :				Optional[Any]      =		number
  
  						# Number not seen before or empty so insert number value
  						if number not in self.numbermap:
  									_lowerCamelCase  :				List[Any]      =		[index]
  
  						# Here we need to perform a binary search insertion in order to insert
  						# The item in the correct place
  						else:
  									_lowerCamelCase  :				Dict      =		self.binary_search_insert(
  									    self.numbermap[number]			,      __A)
  
  
  
  
  
  			def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE)     ->     int:
  						return self.numbermap.get(__A			,      [-1])[0]
  
  
  if __name__ == "__main__":
  	import doctest
  
  	doctest.testmod()
  
  
style_context: 
  
  
  """simple docstring"""
  import timeit
  
  
  
  
  class   lowercase__							:
  
  
  
  
  
     def __init__(       self			,      SCREAMING_SNAKE_CASE)     ->     Tuple:
        if isinstance(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE):  # Initializes a matrix identical to the one provided.
           _lowerCamelCase  :				List[str]      =		arg
           _lowerCamelCase  :				List[str]      =		len(SCREAMING_SNAKE_CASE)
        else:  # Initializes a square matrix of the given size and set values to zero.
           _lowerCamelCase  :				List[Any]      =		arg
           _lowerCamelCase  :				Union[str, Any]      =		[[0 for _ in range(self.n)] for _ in range(self.n)]
  
  
  
  
  
     def __mul__(       self			,      SCREAMING_SNAKE_CASE)     ->     Optional[Any]:
        _lowerCamelCase  :				List[Any]      =		Matrix(self.n)
        for i in range(self.n):
           for j in range(self.n):
              for k in range(self.n):
                 matrix.t[i][j] += self.t[i][k] * b.t[k][j]
        return matrix
  
  
  
  
  
  
  
  def 							_snake_case			(      __snake_case       :			Union[str, Any]	,   __snake_case       :			List[Any]      ):
  
  
  
  
     """simple docstring"""
  
  
  
  
  
  
  
     _lowerCamelCase  :				List[Any]      =		Matrix([[1, 0], [0, 1]]      )
     while b > 0:
        if b & 1:
           matrix *= a
        a *= a
        b >>= 1
     return matrix
  
  def 							_snake_case			(      __snake_case       :			List[str]	,   __snake_case       :			str	,   __snake_case       :			List[Any]      ):
  
  
  
  
     """simple docstring"""
  
  
  
  
  
  
  
     if n == 1:
        return fa
     elif n == 2:
        return fa
     _lowerCamelCase  :				Any      =		Matrix([[1, 1], [1, 0]]      )
     _lowerCamelCase  :				List[str]      =		modular_exponentiation(__snake_case	,   n - 2      )
     return fa * matrix.t[0][0] + fa * matrix.t[0][1]
  
  def 							_snake_case			(      __snake_case       :			int	,   __snake_case       :			Optional[int]	,   __snake_case       :			List[Any]      ):
  
  
  
  
     """simple docstring"""
  
  
  
  
  
  
  
     if n == 1:
        return fa
     elif n == 2:
        return fa
  
     _lowerCamelCase  :				Optional[Any]      =		fa
     _lowerCamelCase  :				int      =		fa
     n -= 2
  
     while n > 0:
        _lowerCamelCase      ,						_lowerCamelCase  :				Tuple      =		fn_a + fn_a, fn_a
        n -= 1
  
     return fn_a
  
  def 							_snake_case			(      ):
  
  
  
  
     """simple docstring"""
  
  
  
  
  
  
  
     _lowerCamelCase  :				List[str]      =		"""
  from random import randint
  from __main__ import fibonacci_with_matrix_exponentiation
  """
     _lowerCamelCase  :				int      =		"""fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"""
     _lowerCamelCase  :				Tuple      =		timeit.timeit(setup=__snake_case	,   stmt=__snake_case	,   number=100      )
     print("""With matrix exponentiation the average execution time is """	,   exec_time / 100      )
     return exec_time
  
  def 							_snake_case			(      ):
  
  
  
  
     """simple docstring"""
  
  
  
  
  
  
  
     _lowerCamelCase  :				Dict      =		"""
  from random import randint
  from __main__ import simple_fibonacci
  """
     _lowerCamelCase  :				Optional[int]      =		"""simple_fibonacci(randint(1,70000), 1, 1)"""
     _lowerCamelCase  :				List[Any]      =		timeit.timeit(setup=__snake_case	,   stmt=__snake_case	,   number=100      )
     print(
         """Without matrix exponentiation the average execution time is """	,   exec_time / 100      )
     return exec_time
  
  def 							_snake_case			(      ):
  
  
  
  
     """simple docstring"""
  
  
  
  
  
  
  
     matrix_exponentiation_time()
     simple_fibonacci_time()
  
  
  if __name__ == "__main__":
   main()
  
  