"""simple docstring"""






from __future__ import annotations

import os
from collections.abc import Mapping

__A			   = tuple[int, int]


class     UpperCAmelCase						:



    """simple docstring"""

    def __init__(   self    ,			_UpperCAmelCase    ,			_UpperCAmelCase							):
       lowercase__:   set[int]					=      vertices
       lowercase__:   dict[EdgeT, int]					=      {
           (min(_UpperCAmelCase							), max(_UpperCAmelCase							)): weight for edge, weight in edges.items()
       }






    def _snake_case			(   self    ,			_UpperCAmelCase    ,			_UpperCAmelCase							):
       self.vertices.add(edge[0]							)
       self.vertices.add(edge[1]							)
       lowercase__:   Dict					=      weight






    def _snake_case			(   self							):
       lowercase__:   Graph					=      Graph({min(self.vertices							)}    ,			{}							)
       lowercase__:   EdgeT
       lowercase__:   int
       lowercase__:   EdgeT
       lowercase__:   int

       while len(subgraph.vertices							) < len(self.vertices							):
          lowercase__:   str					=      max(self.edges.values()							) + 1
          for edge, weight in self.edges.items():
             if (edge[0] in subgraph.vertices) ^ (edge[1] in subgraph.vertices):
                if weight < min_weight:
                   lowercase__:   Dict					=      edge
                   lowercase__:   Tuple					=      weight

          subgraph.add_edge(_UpperCAmelCase    ,			_UpperCAmelCase							)

       return subgraph



def SCREAMING_SNAKE_CASE__			(   __UpperCAmelCase = "p107_network.txt" )  ->  int:
   lowercase__:   str					=      os.path.abspath(os.path.dirname(__UpperCAmelCase ) )
   lowercase__:   str					=      os.path.join(__UpperCAmelCase       ,    __UpperCAmelCase )
   lowercase__:   dict[EdgeT, int]					=      {}
   lowercase__:   list[str]
   lowercase__:   int
   lowercase__:   int

   with open(__UpperCAmelCase ) as f:
      lowercase__:   str					=      f.read().strip().split('''\n''' )

   lowercase__:   List[Any]					=      [line.split(''',''' ) for line in data]

   for edgea in range(1       ,    len(__UpperCAmelCase ) ):
      for edgea in range(__UpperCAmelCase ):
         if adjaceny_matrix[edgea][edgea] != "-":
            lowercase__:   int					=      int(adjaceny_matrix[edgea][edgea] )

   lowercase__:   Graph					=      Graph(set(range(len(__UpperCAmelCase ) ) )       ,    __UpperCAmelCase )

   lowercase__:   Graph					=      graph.prims_algorithm()

   lowercase__:   int					=      sum(graph.edges.values() )
   lowercase__:   int					=      sum(subgraph.edges.values() )

   return initial_total - optimal_total


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

"""simple docstring"""






def SCREAMING_SNAKE_CASE__			(   __UpperCAmelCase       ,    __UpperCAmelCase )  ->  List[str]:
   lowercase__:   Optional[Any]					=      0
   lowercase__:   List[Any]					=      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

      lowercase__:   Tuple					=      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

      lowercase__:   Optional[int]					=      sorted_collection[point]
      if current_item == item:
         return point
      else:
         if point < left:
            lowercase__:   List[Any]					=      left
            lowercase__:   int					=      point
         elif point > right:
            lowercase__:   Dict					=      right
            lowercase__:   List[str]					=      point
         else:
            if item < current_item:
               lowercase__:   int					=      point - 1
            else:
               lowercase__:   int					=      point + 1
   return None



def SCREAMING_SNAKE_CASE__			(   __UpperCAmelCase       ,    __UpperCAmelCase       ,    __UpperCAmelCase       ,    __UpperCAmelCase )  ->  List[str]:

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

   lowercase__:   Optional[int]					=      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 SCREAMING_SNAKE_CASE__			(   __UpperCAmelCase )  ->  List[Any]:
   if collection != sorted(__UpperCAmelCase ):
      raise ValueError('''Collection must be ascending sorted''' )
   return True


if __name__ == "__main__":
       import sys
       __A			   = 0
       if debug == 1:
              __A			   = [1_0, 3_0, 4_0, 4_5, 5_0, 6_6, 7_7, 9_3]
              try:
                     __assert_sorted(collection)
              except ValueError:
                     sys.exit("Sequence must be ascending sorted to apply interpolation search")
              __A			   = 6_7

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