

def       snake_case_ ()     ->      List[str]:
   return [list(range(1_0_0_0 - i   ,  -1_0_0_0 - i   ,  -1	)	) for i in range(1_0_0_0	)]


__UpperCAmelCase						=					generate_large_matrix()
__UpperCAmelCase						=					(
    [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]],
    [[3, 2], [1, 0]],
    [[7, 7, 6]],
    [[7, 7, 6], [-1, -2, -3]],
    grid,
)





def       snake_case_ (__A	:		list[list[int]]	)     ->      List[Any]:
   assert all(row == sorted(_UpperCAmelCase   ,  reverse=_UpperCAmelCase	) for row in grid	)
   assert all(list(_UpperCAmelCase	) == sorted(_UpperCAmelCase   ,  reverse=_UpperCAmelCase	) for col in zip(*_UpperCAmelCase	)	)





def       snake_case_ (__A	:		list[int]	)     ->      Tuple:
   __lowerCAmelCase    :     Dict          =		0
   __lowerCAmelCase    :     Dict          =		len(_UpperCAmelCase	) - 1

   # Edge cases such as no values or all numbers are negative.
   if not array or array[0] < 0:
      return 0

   while right + 1 > left:
      __lowerCAmelCase    :     Optional[int]          =		(left + right) // 2
      __lowerCAmelCase    :     Optional[int]          =		array[mid]

      # Num must be negative and the index must be greater than or equal to 0.
      if num < 0 and array[mid - 1] >= 0:
         return mid

      if num >= 0:
         __lowerCAmelCase    :     Any          =		mid + 1
      else:
         __lowerCAmelCase    :     Union[str, Any]          =		mid - 1
          # No negative numbers so return the last index of the array + 1 which is the length.
   return len(_UpperCAmelCase	)





def       snake_case_ (__A	:		list[list[int]]	)     ->      Optional[int]:
   __lowerCAmelCase    :     Union[str, Any]          =		0
   __lowerCAmelCase    :     Optional[Any]          =		len(grid[0]	)

   for i in range(len(_UpperCAmelCase	)	):
      __lowerCAmelCase    :     List[str]          =		find_negative_index(grid[i][:bound]	)
      total += bound
   return (len(_UpperCAmelCase	) * len(grid[0]	)) - total





def       snake_case_ (__A	:		list[list[int]]	)     ->      int:
   return len([number for row in grid for number in row if number < 0]	)





def       snake_case_ (__A	:		list[list[int]]	)     ->      Dict:
   __lowerCAmelCase    :     Any          =		0
   for row in grid:
      for i, number in enumerate(_UpperCAmelCase	):
         if number < 0:
            total += len(_UpperCAmelCase	) - i
            break
   return total





def       snake_case_ ()     ->      str:
   from timeit import timeit

   print("""Running benchmarks"""	)
   __lowerCAmelCase    :     List[Any]          =		(
       """from __main__ import count_negatives_binary_search, """
       """count_negatives_brute_force, count_negatives_brute_force_with_break, grid"""
   )
   for func in (
       "count_negatives_binary_search",  # took 0.7727 seconds
       "count_negatives_brute_force_with_break",  # took 4.6505 seconds
       "count_negatives_brute_force",  # took 12.8160 seconds
   ):
      __lowerCAmelCase    :     Tuple          =		timeit(f'''{func}(grid=grid)'''   ,  setup=_UpperCAmelCase   ,  number=5_0_0	)
      print(f'''{func}() took {time:0.4f} seconds'''	)


if __name__ == "__main__":
   import doctest

   doctest.testmod()
   benchmark()









"""simple docstring"""
from __future__ import annotations

import os
from collections.abc import Mapping

__UpperCamelCase     :						Optional[Any]						       =  tuple[int, int]







class       a							:



 def __init__(     self				,       _snake_case				,       _snake_case     ):







  """simple docstring"""






  lowerCAmelCase    				= vertices
  lowerCAmelCase    				= {
      (min(_snake_case     ), max(_snake_case     )): weight for edge, weight in edges.items()
  }



 def    UpperCamelCase__  (     self				,       _snake_case				,       _snake_case     ):







  """simple docstring"""






  self.vertices.add(edge[0]     )
  self.vertices.add(edge[1]     )
  lowerCAmelCase    				= weight



 def    UpperCamelCase__  (     self     ):







  """simple docstring"""






  lowerCAmelCase    				= Graph({min(self.vertices     )}				,       {}     )
  lowerCAmelCase    				= 42
  lowerCAmelCase    				= 42
  lowerCAmelCase    				= 42
  lowerCAmelCase    				= 42

  while len(subgraph.vertices     ) < len(self.vertices     ):
   lowerCAmelCase    				= 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:
      lowerCAmelCase    				= edge
      lowerCAmelCase    				= weight

   subgraph.add_edge(_snake_case				,       _snake_case     )

  return subgraph


def 		_SCREAMING_SNAKE_CASE			(_UpperCAmelCase					:    str = "p107_network.txt"			):
 lowerCAmelCase    				= os.path.abspath(os.path.dirname(_UpperCAmelCase			)			)
 lowerCAmelCase    				= os.path.join(_UpperCAmelCase  ,     _UpperCAmelCase			)
 lowerCAmelCase    				= {}
 lowerCAmelCase    				= 42
 lowerCAmelCase    				= 42
 lowerCAmelCase    				= 42

 with open(_UpperCAmelCase			) as f:
  lowerCAmelCase    				= f.read().strip().split('\n'			)

 lowerCAmelCase    				= [line.split(','			) for line in data]

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

 lowerCAmelCase    				= Graph(set(range(len(_UpperCAmelCase			)			)			)  ,     _UpperCAmelCase			)

 lowerCAmelCase    				= graph.prims_algorithm()

 lowerCAmelCase    				= sum(graph.edges.values()			)
 lowerCAmelCase    				= sum(subgraph.edges.values()			)

 return initial_total - optimal_total


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





