

"""simple docstring"""
import itertools
import os
import re


_A							=  re.compile(R"""([A-Z]+)([A-Z][a-z])""")
_A							=  re.compile(R"""([a-z\d])([A-Z])""")

_A							=  re.compile(R"""(?<!_)_(?!_)""")
_A							=  re.compile(R"""(_{2,})""")

_A							=  R"""^\w+(\.\w+)*$"""

_A							=  R"""<>:/\|?*"""




def 					a__						(						lowerCAmelCase    )	-> Optional[Any]:
      UpperCAmelCase__			:							List[str]							=    _uppercase_uppercase_re.sub(R"""\1_\2"""			,	lowerCAmelCase    )
      UpperCAmelCase__			:							Dict							=    _lowercase_uppercase_re.sub(R"""\1_\2"""			,	lowerCAmelCase    )
      return name.lower()




def 					a__						(						lowerCAmelCase    )	-> int:
      UpperCAmelCase__			:							List[str]							=    _single_underscore_re.split(lowerCAmelCase    )
      UpperCAmelCase__			:							List[str]							=    [_multiple_underscores_re.split(lowerCAmelCase    ) for n in name]
      return "".join(n.capitalize() for n in itertools.chain.from_iterable(lowerCAmelCase    ) if n != """"""    )




def 					a__						(						lowerCAmelCase    )	-> Any:
      if os.path.basename(lowerCAmelCase    ) != name:
            raise ValueError(F"""Should be a dataset name, not a path: {name}"""    )
      return camelcase_to_snakecase(lowerCAmelCase    )




def 					a__						(						lowerCAmelCase			,	lowerCAmelCase    )	-> int:
      if os.path.basename(lowerCAmelCase    ) != name:
            raise ValueError(F"""Should be a dataset name, not a path: {name}"""    )
      if not re.match(_split_re			,	lowerCAmelCase    ):
            raise ValueError(F"""Split name should match '{_split_re}'' but got '{split}'."""    )
      return F"""{filename_prefix_for_name(lowerCAmelCase    )}-{split}"""




def 					a__						(						lowerCAmelCase			,	lowerCAmelCase			,	lowerCAmelCase			,	lowerCAmelCase=None    )	-> int:
      UpperCAmelCase__			:							Tuple							=    filename_prefix_for_split(lowerCAmelCase			,	lowerCAmelCase    )
      if filetype_suffix:
            prefix += F""".{filetype_suffix}"""
      UpperCAmelCase__			:							List[str]							=    os.path.join(lowerCAmelCase			,	lowerCAmelCase    )
      return F"""{filepath}*"""





def 					a__						(						lowerCAmelCase			,	lowerCAmelCase			,	lowerCAmelCase			,	lowerCAmelCase=None			,	lowerCAmelCase=None    )	-> Union[str, Any]:
      UpperCAmelCase__			:							List[str]							=    filename_prefix_for_split(lowerCAmelCase			,	lowerCAmelCase    )
      UpperCAmelCase__			:							Union[str, Any]							=    os.path.join(lowerCAmelCase			,	lowerCAmelCase    )

      if shard_lengths:
            UpperCAmelCase__			:							int							=    len(lowerCAmelCase    )
            UpperCAmelCase__			:							Dict							=    [F"""{prefix}-{shard_id:05d}-of-{num_shards:05d}""" for shard_id in range(lowerCAmelCase    )]
            if filetype_suffix:
                  UpperCAmelCase__			:							List[Any]							=    [filename + F""".{filetype_suffix}""" for filename in filenames]
            return filenames
      else:
            UpperCAmelCase__			:							List[str]							=    prefix
            if filetype_suffix:
                  filename += F""".{filetype_suffix}"""
            return [filename]


"""simple docstring"""



def 	_lowerCamelCase(	a   ,    a				):
       __a       =    0
       __a       =    len(a				) - 1

       while left <= right:
              # avoid divided by 0 during interpolation
              if sorted_collection[left] == sorted_collection[right]:
                     if sorted_collection[left] == item:
                            return left
                     else:
                            return None

              __a       =    left + ((item - sorted_collection[left]) * (right - left)) // (
                  sorted_collection[right] - sorted_collection[left]
              )

              # out of range check
              if point < 0 or point >= len(a				):
                     return None

              __a       =    sorted_collection[point]
              if current_item == item:
                     return point
              else:
                     if point < left:
                            __a       =    left
                            __a       =    point
                     elif point > right:
                            __a       =    right
                            __a       =    point
                     else:
                            if item < current_item:
                                   __a       =    point - 1
                            else:
                                   __a       =    point + 1
       return None



def 	_lowerCamelCase(	a   ,    a   ,    a   ,    a				):

       # avoid divided by 0 during interpolation
       if sorted_collection[left] == sorted_collection[right]:
              if sorted_collection[left] == item:
                     return left
              else:
                     return None

       __a       =    left + ((item - sorted_collection[left]) * (right - left)) // (
           sorted_collection[right] - sorted_collection[left]
       )

       # out of range check
       if point < 0 or point >= len(a				):
              return None

       if sorted_collection[point] == item:
              return point
       elif point < left:
              return interpolation_search_by_recursion(a   ,    a   ,    a   ,    a				)
       elif point > right:
              return interpolation_search_by_recursion(a   ,    a   ,    a   ,    a				)
       else:
              if sorted_collection[point] > item:
                     return interpolation_search_by_recursion(
                         a   ,    a   ,    a   ,    point - 1				)
              else:
                     return interpolation_search_by_recursion(
                         a   ,    a   ,    point + 1   ,    a				)



def 	_lowerCamelCase(	a				):
       if collection != sorted(a				):
              raise ValueError("Collection must be ascending sorted"				)
       return True


if __name__ == "__main__":
   import sys
   SCREAMING_SNAKE_CASE__:List[str]									=			0
   if debug == 1:
      SCREAMING_SNAKE_CASE__:Tuple									=			[10, 30, 40, 45, 50, 66, 77, 93]
      try:
         __assert_sorted(collection)
      except ValueError:
         sys.exit("""Sequence must be ascending sorted to apply interpolation search""")
      SCREAMING_SNAKE_CASE__:int									=			67

   SCREAMING_SNAKE_CASE__:List[str]									=			interpolation_search(collection, target)
   if result is not None:
      print(F'''{target} found at positions: {result}''')
   else:
      print("""Not found""")
