from functools import lru_cache






@lru_cache
def    UpperCAmelCase__(						lowerCamelCase_  ):



			"""simple docstring"""





			if not isinstance(__a							,	__a  ):
						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    UpperCAmelCase__(						lowerCamelCase_							,	lowerCamelCase_  ):



			"""simple docstring"""





			_snake_case              =      len(__a  )
			# Find m such that F_m >= n where F_i is the i_th fibonacci number.
			_snake_case              =      0
			while True:
						if fibonacci(__a  ) >= 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()





import unittest

from transformers import BlenderbotTokenizer, BlenderbotTokenizerFast
from transformers.utils import cached_property

class 	_SCREAMING_SNAKE_CASE							(     unittest.TestCase							):






		"""simple docstring"""







		@cached_property
		def 				_a				(			self    :				Tuple   ):






					"""simple docstring"""
					return BlenderbotTokenizer.from_pretrained("facebook/blenderbot-3B"   )



		@cached_property
		def 				_a				(			self    :				Tuple   ):






					"""simple docstring"""
					return BlenderbotTokenizerFast.from_pretrained("facebook/blenderbot-3B"   )



		def 				_a				(			self    :				Optional[Any]   ):






					"""simple docstring"""
					_snake_case              =      self.tokenizer_ab
					_snake_case              =      " I am a small frog."
					_snake_case              =      tok([src_text]  ,					padding=__SCREAMING_SNAKE_CASE  ,					truncation=__SCREAMING_SNAKE_CASE   )["input_ids"]
					_snake_case              =      tok.batch_decode(__SCREAMING_SNAKE_CASE  ,					skip_special_tokens=__SCREAMING_SNAKE_CASE  ,					clean_up_tokenization_spaces=__SCREAMING_SNAKE_CASE   )[0]
					assert src_text == decoded



		def 				_a				(			self    :				str   ):






					"""simple docstring"""
					_snake_case              =      self.rust_tokenizer_ab
					_snake_case              =      " I am a small frog."
					_snake_case              =      tok([src_text]  ,					padding=__SCREAMING_SNAKE_CASE  ,					truncation=__SCREAMING_SNAKE_CASE   )["input_ids"]
					_snake_case              =      tok.batch_decode(__SCREAMING_SNAKE_CASE  ,					skip_special_tokens=__SCREAMING_SNAKE_CASE  ,					clean_up_tokenization_spaces=__SCREAMING_SNAKE_CASE   )[0]
					assert src_text == decoded



		def 				_a				(			self    :				Optional[Any]   ):






					"""simple docstring"""
					assert self.tokenizer_ab.add_prefix_space
					assert self.tokenizer_ab([" Sam", "Sam"]   ).input_ids == [[5_502, 2], [5_502, 2]]







		def 				_a				(			self    :				str   ):






					"""simple docstring"""
					assert self.rust_tokenizer_ab.add_prefix_space
					assert self.rust_tokenizer_ab([" Sam", "Sam"]   ).input_ids == [[5_502, 2], [5_502, 2]]

