



def 						a__     (						_UpperCamelCase     :	List[str]	,_UpperCamelCase     :	int	,_UpperCamelCase     :	Dict	,_UpperCamelCase     :	Union[str, Any]							):
   if start == end:
      return start if lst[start] > item else start + 1
   if start > end:
      return start

   __lowerCamelCase  							=      (start + end) // 2
   if lst[mid] < item:
      return binary_search(_UpperCamelCase	,_UpperCamelCase	,mid + 1	,_UpperCamelCase							)
   elif lst[mid] > item:
      return binary_search(_UpperCamelCase	,_UpperCamelCase	,_UpperCamelCase	,mid - 1							)
   else:
      return mid





def 						a__     (						_UpperCamelCase     :	Tuple							):
   __lowerCamelCase  							=      len(_UpperCamelCase							)

   for index in range(1	,_UpperCamelCase							):
      __lowerCamelCase  							=      lst[index]
      __lowerCamelCase  							=      binary_search(_UpperCamelCase	,_UpperCamelCase	,0	,index - 1							)
      __lowerCamelCase  							=      lst[:pos] + [value] + lst[pos:index] + lst[index + 1 :]

   return lst





def 						a__     (						_UpperCamelCase     :	int	,_UpperCamelCase     :	int							):
   if not left:
      return right

   if not right:
      return left

   if left[0] < right[0]:
      return [left[0], *merge(left[1:]	,_UpperCamelCase							)]

   return [right[0], *merge(_UpperCamelCase	,right[1:]							)]





def 						a__     (						_UpperCamelCase     :	str							):
   __lowerCamelCase  							=      len(_UpperCamelCase							)
   __lowerCamelCase							,__lowerCamelCase  							=      [], []
   __lowerCamelCase  							=      [lst[0]]
   __lowerCamelCase  							=      []
   __lowerCamelCase  							=      1
   while i < length:
      if lst[i] < lst[i - 1]:
         runs.append(_UpperCamelCase							)
         __lowerCamelCase  							=      [lst[i]]
      else:
         new_run.append(lst[i]							)
      i += 1
   runs.append(_UpperCamelCase							)

   for run in runs:
      sorted_runs.append(insertion_sort(_UpperCamelCase							)							)
   for run in sorted_runs:
      __lowerCamelCase  							=      merge(_UpperCamelCase	,_UpperCamelCase							)

   return sorted_array





def 						a__     (						):
   __lowerCamelCase  							=      [5, 9, 10, 3, -4, 5, 1_78, 92, 46, -18, 0, 7]
   __lowerCamelCase  							=      tim_sort(_UpperCamelCase							)
   print(_UpperCamelCase							)


if __name__ == "__main__":
  main()











from typing import Optional, Tuple

from ...tokenization_utils_fast import PreTrainedTokenizerFast
from ...utils import logging
from .tokenization_openai import OpenAIGPTTokenizer


a_								=   logging.get_logger(__name__)

a_								=   {"""vocab_file""": """vocab.json""", """merges_file""": """merges.txt""", """tokenizer_file""": """tokenizer.json"""}

a_								=   {
    """vocab_file""": {"""openai-gpt""": """https://huggingface.co/openai-gpt/resolve/main/vocab.json"""},
    """merges_file""": {"""openai-gpt""": """https://huggingface.co/openai-gpt/resolve/main/merges.txt"""},
    """tokenizer_file""": {"""openai-gpt""": """https://huggingface.co/openai-gpt/resolve/main/tokenizer.json"""},
}

a_								=   {
    """openai-gpt""": 512,
}



class 	__lowerCAmelCase       (		lowerCAmelCase__				):
 lowerCAmelCase__       =					VOCAB_FILES_NAMES
 lowerCAmelCase__       =					PRETRAINED_VOCAB_FILES_MAP
 lowerCAmelCase__       =					PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
 lowerCAmelCase__       =					["""input_ids""", """attention_mask"""]
 lowerCAmelCase__       =					OpenAIGPTTokenizer




 def __init__(  self		,			__UpperCAmelCase=None		,			__UpperCAmelCase=None		,			__UpperCAmelCase=None		,			__UpperCAmelCase="<unk>"		,			**__UpperCAmelCase			):



    '''simple docstring'''
    super().__init__(__UpperCAmelCase		,			__UpperCAmelCase		,			tokenizer_file=__UpperCAmelCase		,			unk_token=__UpperCAmelCase		,			**__UpperCAmelCase			)




 @property
 def     lowerCamelCase (  self			):



    '''simple docstring'''
    return True




 def     lowerCamelCase (  self		,			__UpperCAmelCase		,			__UpperCAmelCase = None			):



    '''simple docstring'''
    __lowerCamelCase  							=      self._tokenizer.model.save(__UpperCAmelCase		,			name=__UpperCAmelCase			)
    return tuple(__UpperCAmelCase			)






