





"""simple docstring"""


from functools import lru_cache





@lru_cache
def 				a__      (	_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 				a__      (	_UpperCAmelCase						,  _UpperCAmelCase						)     ->	int:

 '''simple docstring'''






 snake_case__     				=					len(_UpperCAmelCase						)
 # Find m such that F_m >= n where F_i is the i_th fibonacci number.
 snake_case__     				=					0
 while True:
  if fibonacci(_UpperCAmelCase						) >= len_list:
   snake_case__     				=					i
   break
  i += 1
 snake_case__     				=					0
 while fibb_k > 0:
  snake_case__     				=					min(
      offset + fibonacci(fibb_k - 1						)						,  len_list - 1						)  # Prevent out of range
  snake_case__     				=					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 typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_tokenizers_available, is_torch_available


_UpperCamelCase:					Optional[Any]     				=	{
    'configuration_codegen': ['CODEGEN_PRETRAINED_CONFIG_ARCHIVE_MAP', 'CodeGenConfig', 'CodeGenOnnxConfig'],
    'tokenization_codegen': ['CodeGenTokenizer'],
}

try:
     if not is_tokenizers_available():
          raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
     pass
else:
     _UpperCamelCase:					Union[str, Any]     				=	['CodeGenTokenizerFast']

try:
     if not is_torch_available():
          raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
     pass
else:
     _UpperCamelCase:					str     				=	[
         'CODEGEN_PRETRAINED_MODEL_ARCHIVE_LIST',
         'CodeGenForCausalLM',
         'CodeGenModel',
         'CodeGenPreTrainedModel',
     ]

if TYPE_CHECKING:
     from .configuration_codegen import CODEGEN_PRETRAINED_CONFIG_ARCHIVE_MAP, CodeGenConfig, CodeGenOnnxConfig
     from .tokenization_codegen import CodeGenTokenizer

     try:
          if not is_tokenizers_available():
               raise OptionalDependencyNotAvailable()
     except OptionalDependencyNotAvailable:
          pass
     else:
          from .tokenization_codegen_fast import CodeGenTokenizerFast

     try:
          if not is_torch_available():
               raise OptionalDependencyNotAvailable()
     except OptionalDependencyNotAvailable:
          pass
     else:
          from .modeling_codegen import (
              CODEGEN_PRETRAINED_MODEL_ARCHIVE_LIST,
              CodeGenForCausalLM,
              CodeGenModel,
              CodeGenPreTrainedModel,
          )

else:
     import sys

     _UpperCamelCase:					int     				=	_LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)
