



"""simple docstring"""




from functools import lru_cache


@lru_cache
def 	lowercase__  (      _UpperCAmelCase					)  ->      int:






      '''simple docstring'''


      if not isinstance(_UpperCAmelCase						,   _UpperCAmelCase					):
            raise TypeError('k must be an integer.'					)
      if k < 0:
            raise ValueError('k integer must be greater or equal to zero.'					)
      if k == 0:
            return 0
      elif k == 1:
            return 1
      else:
            return fibonacci(k - 1					) + fibonacci(k - 2					)


def 	lowercase__  (      _UpperCAmelCase						,   _UpperCAmelCase					)  ->      int:






      '''simple docstring'''


      lowercase	:   Optional[int]											= len(_UpperCAmelCase					)
      # Find m such that F_m >= n where F_i is the i_th fibonacci number.
      lowercase	:   Optional[Any]											= 0
      while True:
            if fibonacci(_UpperCAmelCase					) >= len_list:
                  lowercase	:   Tuple											= i
                  break
            i += 1
      lowercase	:   int											= 0
      while fibb_k > 0:
            lowercase	:   List[Any]											= min(
                offset + fibonacci(fibb_k - 1					)						,   len_list - 1					)  # Prevent out of range
            lowercase	:   List[Any]											= arr[index_k]
            if item_k_1 == val:
                  return index_k
            elif val < item_k_1:
                  fibb_k -= 1
            elif val > item_k_1:
                  offset += fibonacci(fibb_k - 1					)
                  fibb_k -= 2
      else:
            return -1


if __name__ == "__main__":
     import doctest

     doctest.testmod()





"""simple docstring"""




from __future__ import annotations

from typing import Generic, TypeVar

_UpperCamelCase:					str     				=	TypeVar('T')


class 	a__		(    Generic[T]  ):


   def __init__(				self   :				Optional[int],  lowerCAmelCase   :				T      )     ->							List[Any]:
         lowercase	:   Optional[int]											= data  # Assign data
         lowercase	:   Node[T] | None											= None  # Initialize next as null
         lowercase	:   Node[T] | None											= None  # Initialize prev as null




class 	a__		(    Generic[T]  ):


   def __init__(				self   :				Optional[int]      )     ->							None:
         lowercase	:   Node[T] | None											= None


   def 							lowercase					(				self   :				Any,  lowerCAmelCase   :				T      )     ->							None:
         if self.head is None:
               lowercase	:   Tuple											= Node(lowerCAmelCase      )
         else:
               lowercase	:   Dict											= Node(lowerCAmelCase      )
               lowercase	:   str											= new_node
               lowercase	:   int											= self.head
               lowercase	:   List[str]											= None
               lowercase	:   List[str]											= new_node


   def 							lowercase					(				self   :				Dict      )     ->							T | None:
         if self.head is None:
               return None
         else:
               assert self.head is not None
               lowercase	:   Optional[int]											= self.head.data
               lowercase	:   Any											= self.head.next
               if self.head is not None:
                     lowercase	:   Optional[Any]											= None
               return temp


   def 							lowercase					(				self   :				List[Any]      )     ->							T | None:
         return self.head.data if self.head is not None else None


   def __len__(				self   :				int      )     ->							int:
         lowercase	:   Any											= self.head
         lowercase	:   List[Any]											= 0
         while temp is not None:
               count += 1
               lowercase	:   Any											= temp.next
         return count


   def 							lowercase					(				self   :				List[Any]      )     ->							bool:
         return self.head is None






   def 							lowercase					(				self   :				Optional[int]      )     ->							None:
         print('stack elements are:'      )
         lowercase	:   Optional[int]											= self.head
         while temp is not None:
               print(temp.data,  end='->'      )
               lowercase	:   List[str]											= temp.next


# Code execution starts here
if __name__ == "__main__":
     # Start with the empty stack
     _UpperCamelCase:					Stack[int]     				=	Stack()

     # Insert 4 at the beginning. So stack becomes 4->None
     print('Stack operations using Doubly LinkedList')
     stack.push(4)

     # Insert 5 at the beginning. So stack becomes 4->5->None
     stack.push(5)

     # Insert 6 at the beginning. So stack becomes 4->5->6->None
     stack.push(6)

     # Insert 7 at the beginning. So stack becomes 4->5->6->7->None
     stack.push(7)

     # Print the stack
     stack.print_stack()

     # Print the top element
     print('\nTop element is ', stack.top())

     # Print the stack size
     print('Size of the stack is ', len(stack))

     # pop the top element
     stack.pop()

     # pop the top element
     stack.pop()

     # two elements have now been popped off
     stack.print_stack()

     # Print True if the stack is empty else False
     print('\nstack is empty:', stack.is_empty())
