



def      _A				()  ->list[list[int]]:



			'''simple docstring'''







			return [list(range(1000 - i      ,			-1000 - i      ,			-1 ) ) for i in range(1000 )]


_lowercase     							=						generate_large_matrix()
_lowercase     							=						(
    [[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      _A				(UpperCamelCase		:      list[list[int]] )  ->None:



			'''simple docstring'''







			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      _A				(UpperCamelCase		:      list[int] )  ->int:



			'''simple docstring'''







			lowerCamelCase__ :      Tuple								=		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__ :      str								=		(left + right) // 2
						lowerCamelCase__ :      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__ :      Optional[Any]								=		mid + 1
						else:
									lowerCamelCase__ :      List[Any]								=		mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
			return len(UpperCamelCase )






def      _A				(UpperCamelCase		:      list[list[int]] )  ->int:



			'''simple docstring'''







			lowerCamelCase__ :      Optional[Any]								=		0
			lowerCamelCase__ :      Optional[int]								=		len(grid[0] )

			for i in range(len(UpperCamelCase ) ):
						lowerCamelCase__ :      Optional[int]								=		find_negative_index(grid[i][:bound] )
						total += bound
			return (len(UpperCamelCase ) * len(grid[0] )) - total






def      _A				(UpperCamelCase		:      list[list[int]] )  ->int:



			'''simple docstring'''







			return len([number for row in grid for number in row if number < 0] )






def      _A				(UpperCamelCase		:      list[list[int]] )  ->int:



			'''simple docstring'''







			lowerCamelCase__ :      List[Any]								=		0
			for row in grid:
						for i, number in enumerate(UpperCamelCase ):
									if number < 0:
												total += len(UpperCamelCase ) - i
												break
			return total






def      _A				()  ->None:



			'''simple docstring'''







			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__ :      Optional[Any]								=		timeit(f"{func}(grid=grid)"      ,			setup=UpperCamelCase      ,			number=500 )
						print(f"{func}() took {time:0.4f} seconds" )


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				benchmark()








import unittest

from .lib import (
    Matrix,
    Vector,
    axpy,
    square_zero_matrix,
    unit_basis_vector,
    zero_vector,
)
class 				__A					( unittest.TestCase      ):





			def        _snake_case    (self				):
						lowerCamelCase__ :      List[str]								=		Vector([1, 2, 3]				)
						self.assertEqual(x.component(0				)							,    1				)
						self.assertEqual(x.component(2				)							,    3				)
						lowerCamelCase__ :      str								=		Vector()





			def        _snake_case    (self				):
						lowerCamelCase__ :      Dict								=		Vector([0, 0, 0, 0, 0, 1]				)
						self.assertEqual(str(__magic_name__				)							,    """(0,0,0,0,0,1)"""				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      Tuple								=		Vector([1, 2, 3, 4]				)
						self.assertEqual(len(__magic_name__				)							,    4				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      Dict								=		Vector([1, 2]				)
						lowerCamelCase__ :      str								=		Vector([1, 2, 3, 4, 5]				)
						lowerCamelCase__ :      int								=		Vector([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]				)
						lowerCamelCase__ :      int								=		Vector([1, -1, 1, -1, 2, -3, 4, -5]				)
						self.assertAlmostEqual(x.euclidean_length()							,    2.2_36							,    3				)
						self.assertAlmostEqual(y.euclidean_length()							,    7.4_16							,    3				)
						self.assertEqual(z.euclidean_length()							,    0				)
						self.assertAlmostEqual(w.euclidean_length()							,    7.6_16							,    3				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      str								=		Vector([1, 2, 3]				)
						lowerCamelCase__ :      Union[str, Any]								=		Vector([1, 1, 1]				)
						self.assertEqual((x + y).component(0				)							,    2				)
						self.assertEqual((x + y).component(1				)							,    3				)
						self.assertEqual((x + y).component(2				)							,    4				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      Optional[int]								=		Vector([1, 2, 3]				)
						lowerCamelCase__ :      Any								=		Vector([1, 1, 1]				)
						self.assertEqual((x - y).component(0				)							,    0				)
						self.assertEqual((x - y).component(1				)							,    1				)
						self.assertEqual((x - y).component(2				)							,    2				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      Dict								=		Vector([1, 2, 3]				)
						lowerCamelCase__ :      int								=		Vector([2, -1, 4]				)  # for test of dot product
						lowerCamelCase__ :      List[Any]								=		Vector([1, -2, -1]				)
						self.assertEqual(str(x * 3.0				)							,    """(3.0,6.0,9.0)"""				)
						self.assertEqual((a * b)							,    0				)





			def        _snake_case    (self				):
						self.assertEqual(str(zero_vector(10				)				).count("""0"""				)							,    10				)





			def        _snake_case    (self				):
						self.assertEqual(str(unit_basis_vector(3							,    1				)				)							,    """(0,1,0)"""				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      Any								=		Vector([1, 2, 3]				)
						lowerCamelCase__ :      str								=		Vector([1, 0, 1]				)
						self.assertEqual(str(axpy(2							,    __magic_name__							,    __magic_name__				)				)							,    """(3,4,7)"""				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      Optional[Any]								=		Vector([1, 0, 0, 0, 0, 0]				)
						lowerCamelCase__ :      int								=		x.copy()
						self.assertEqual(str(__magic_name__				)							,    str(__magic_name__				)				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      int								=		Vector([1, 0, 0]				)
						x.change_component(0							,    0				)
						x.change_component(1							,    1				)
						self.assertEqual(str(__magic_name__				)							,    """(0,1,0)"""				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      Optional[Any]								=		Matrix([[1, 2, 3], [2, 4, 5], [6, 7, 8]]							,    3							,    3				)
						self.assertEqual("""|1,2,3|\n|2,4,5|\n|6,7,8|\n"""							,    str(__magic_name__				)				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      int								=		Matrix([[1, 2, 3], [2, 4, 5], [6, 7, 8]]							,    3							,    3				)
						lowerCamelCase__ :      int								=		[[-3, -14, -10], [-5, -10, -5], [-2, -1, 0]]
						for x in range(a.height()				):
									for y in range(a.width()				):
												self.assertEqual(minors[x][y]							,    a.minor(__magic_name__							,    __magic_name__				)				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      Any								=		Matrix([[1, 2, 3], [2, 4, 5], [6, 7, 8]]							,    3							,    3				)
						lowerCamelCase__ :      Optional[Any]								=		[[-3, 14, -10], [5, -10, 5], [-2, 1, 0]]
						for x in range(a.height()				):
									for y in range(a.width()				):
												self.assertEqual(cofactors[x][y]							,    a.cofactor(__magic_name__							,    __magic_name__				)				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      Optional[int]								=		Matrix([[1, 2, 3], [2, 4, 5], [6, 7, 8]]							,    3							,    3				)
						self.assertEqual(-5							,    a.determinant()				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      List[str]								=		Matrix([[1, 2, 3], [4, 5, 6], [7, 8, 9]]							,    3							,    3				)
						lowerCamelCase__ :      Optional[int]								=		Vector([1, 2, 3]				)
						self.assertEqual("""(14,32,50)"""							,    str(a * x				)				)
						self.assertEqual("""|2,4,6|\n|8,10,12|\n|14,16,18|\n"""							,    str(a * 2				)				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      str								=		Matrix([[1, 2, 3], [2, 4, 5], [6, 7, 8]]							,    3							,    3				)
						a.change_component(0							,    2							,    5				)
						self.assertEqual("""|1,2,5|\n|2,4,5|\n|6,7,8|\n"""							,    str(__magic_name__				)				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      List[Any]								=		Matrix([[1, 2, 3], [2, 4, 5], [6, 7, 8]]							,    3							,    3				)
						self.assertEqual(7							,    a.component(2							,    1				)							,    0.01				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      Tuple								=		Matrix([[1, 2, 3], [2, 4, 5], [6, 7, 8]]							,    3							,    3				)
						lowerCamelCase__ :      int								=		Matrix([[1, 2, 7], [2, 4, 5], [6, 7, 10]]							,    3							,    3				)
						self.assertEqual("""|2,4,10|\n|4,8,10|\n|12,14,18|\n"""							,    str(a + b				)				)





			def        _snake_case    (self				):
						lowerCamelCase__ :      str								=		Matrix([[1, 2, 3], [2, 4, 5], [6, 7, 8]]							,    3							,    3				)
						lowerCamelCase__ :      Optional[Any]								=		Matrix([[1, 2, 7], [2, 4, 5], [6, 7, 10]]							,    3							,    3				)
						self.assertEqual("""|0,0,-4|\n|0,0,0|\n|0,0,-2|\n"""							,    str(a - b				)				)





			def        _snake_case    (self				):
						self.assertEqual(
						    """|0,0,0,0,0|\n|0,0,0,0,0|\n|0,0,0,0,0|\n|0,0,0,0,0|\n|0,0,0,0,0|\n"""							,    str(square_zero_matrix(5				)				)							,    )


if __name__ == "__main__":
				unittest.main()



