





'''simple docstring'''






import os

snake_case_     =	{"""I""": 1, """V""": 5, """X""": 10, """L""": 50, """C""": 1_00, """D""": 5_00, """M""": 10_00}
def 							_lowerCamelCase(  UpperCamelCase__    : str		)		->  int:
    A       :       List[str]							=						0

    A       :       List[Any]							=						0
    while index < len(UpperCamelCase__		) - 1:
        A       :       int							=						SYMBOLS[numerals[index]]
        A       :       Optional[int]							=						SYMBOLS[numerals[index + 1]]
        if current_value < next_value:
            total_value -= current_value
        else:
            total_value += current_value
        index += 1
    total_value += SYMBOLS[numerals[index]]

    return total_value
def 							_lowerCamelCase(  UpperCamelCase__    : int		)		->  str:
    A       :       Union[str, Any]							=						''''''

    A       :       Union[str, Any]							=						num // 1_000
    numerals += m_count * "M"
    num %= 1_000

    A       :       List[Any]							=						num // 100
    if c_count == 9:
        numerals += "CM"
        c_count -= 9
    elif c_count == 4:
        numerals += "CD"
        c_count -= 4
    if c_count >= 5:
        numerals += "D"
        c_count -= 5
    numerals += c_count * "C"
    num %= 100

    A       :       Optional[int]							=						num // 10
    if x_count == 9:
        numerals += "XC"
        x_count -= 9
    elif x_count == 4:
        numerals += "XL"
        x_count -= 4
    if x_count >= 5:
        numerals += "L"
        x_count -= 5
    numerals += x_count * "X"
    num %= 10

    if num == 9:
        numerals += "IX"
        num -= 9
    elif num == 4:
        numerals += "IV"
        num -= 4
    if num >= 5:
        numerals += "V"
        num -= 5
    numerals += num * "I"

    return numerals
def 							_lowerCamelCase(  UpperCamelCase__    : str = "/p089_roman.txt"		)		->  int:
    A       :       List[Any]							=						0

    with open(os.path.dirname(UpperCamelCase__		) + roman_numerals_filename		) as filea:
        A       :       List[str]							=						filea.readlines()

    for line in lines:
        A       :       str							=						line.strip()
        A       :       Optional[Any]							=						parse_roman_numerals(UpperCamelCase__		)
        A       :       List[Any]							=						generate_roman_numerals(UpperCamelCase__		)
        savings += len(UpperCamelCase__		) - len(UpperCamelCase__		)

    return savings


if __name__ == "__main__":
     print(f'''{solution() = }''')







'''simple docstring'''






def 							_lowerCamelCase(  UpperCamelCase__    : Optional[int]    ,       UpperCamelCase__    : str		)		->  Optional[int]:
    A       :       Optional[int]							=						0
    A       :       str							=						len(UpperCamelCase__		) - 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       :       Any							=						left + ((item - sorted_collection[left]) * (right - left)) // (
            sorted_collection[right] - sorted_collection[left]
        )

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

        A       :       Union[str, Any]							=						sorted_collection[point]
        if current_item == item:
            return point
        else:
            if point < left:
                A       :       Tuple							=						left
                A       :       Tuple							=						point
            elif point > right:
                A       :       Optional[Any]							=						right
                A       :       str							=						point
            else:
                if item < current_item:
                    A       :       Tuple							=						point - 1
                else:
                    A       :       Optional[Any]							=						point + 1
    return None
def 							_lowerCamelCase(  UpperCamelCase__    : Dict    ,       UpperCamelCase__    : str    ,       UpperCamelCase__    : Dict    ,       UpperCamelCase__    : List[str]		)		->  List[Any]:

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

    A       :       Dict							=						left + ((item - sorted_collection[left]) * (right - left)) // (
        sorted_collection[right] - sorted_collection[left]
    )

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

    if sorted_collection[point] == item:
        return point
    elif point < left:
        return interpolation_search_by_recursion(UpperCamelCase__    ,       UpperCamelCase__    ,       UpperCamelCase__    ,       UpperCamelCase__		)
    elif point > right:
        return interpolation_search_by_recursion(UpperCamelCase__    ,       UpperCamelCase__    ,       UpperCamelCase__    ,       UpperCamelCase__		)
    else:
        if sorted_collection[point] > item:
            return interpolation_search_by_recursion(
                UpperCamelCase__    ,       UpperCamelCase__    ,       UpperCamelCase__    ,       point - 1		)
        else:
            return interpolation_search_by_recursion(
                UpperCamelCase__    ,       UpperCamelCase__    ,       point + 1    ,       UpperCamelCase__		)
def 							_lowerCamelCase(  UpperCamelCase__    : Optional[int]		)		->  List[Any]:
    if collection != sorted(UpperCamelCase__		):
        raise ValueError('''Collection must be ascending sorted'''		)
    return True


if __name__ == "__main__":
     import sys
     snake_case_     =	0
     if debug == 1:
          snake_case_     =	[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""")
          snake_case_     =	67

     snake_case_     =	interpolation_search(collection, target)
     if result is not None:
          print(f'''{target} found at positions: {result}''')
     else:
          print("""Not found""")
