"""simple docstring"""







def      __lowerCAmelCase(		):






	"""simple docstring"""





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


SCREAMING_SNAKE_CASE									=						generate_large_matrix()
SCREAMING_SNAKE_CASE									=						(
    [[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      __lowerCAmelCase(		__UpperCAmelCase			):






	"""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      __lowerCAmelCase(		__UpperCAmelCase			):






	"""simple docstring"""





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


def      __lowerCAmelCase(		__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    List[Any]							=							0
	_lowercase :    List[str]							=							len(grid[0]			)

	for i in range(len(__UpperCAmelCase			)			):
		_lowercase :    Tuple							=							find_negative_index(grid[i][:bound]			)
		total += bound
	return (len(__UpperCAmelCase			) * len(grid[0]			)) - total


def      __lowerCAmelCase(		__UpperCAmelCase			):






	"""simple docstring"""





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


def      __lowerCAmelCase(		__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    str							=							0
	for row in grid:
		for i, number in enumerate(__UpperCAmelCase			):
			if number < 0:
				total += len(__UpperCAmelCase			) - i
				break
	return total


def      __lowerCAmelCase(		):






	"""simple docstring"""





	from timeit import timeit

	print('Running benchmarks'			)
	_lowercase :    List[str]							=							(
	    '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
	):
		_lowercase :    Union[str, 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()




"""simple docstring"""







from __future__ import annotations



class  _lowerCamelCase			:







				def __init__( self    :       Any			,					lowerCamelCase_    :       list[list[int]]						):

					"""simple docstring"""






					_lowercase :    Tuple							=							TypeError(
					    'Matrices must be formed from a list of zero or more lists containing at '
					    'least one and the same number of values, each of which must be of type '
					    'int or float.'						)
					if len(lowerCamelCase_						) != 0:
						_lowercase :    Dict							=							len(rows[0]						)
						if cols == 0:
							raise error
						for row in rows:
							if len(lowerCamelCase_						) != cols:
								raise error
							for value in row:
								if not isinstance(lowerCamelCase_			,					(int, float)						):
									raise error
						_lowercase :    int							=							rows
					else:
						_lowercase :    Optional[Any]							=							[]







				def 							__UpperCAmelCase					( self    :       List[str]						):

					"""simple docstring"""






					return [[row[i] for row in self.rows] for i in range(len(self.rows[0]						)						)]







				@property
				def 							__UpperCAmelCase					( self    :       List[str]						):

					"""simple docstring"""






					return len(self.rows						)







				@property
				def 							__UpperCAmelCase					( self    :       int						):

					"""simple docstring"""






					return len(self.rows[0]						)







				@property
				def 							__UpperCAmelCase					( self    :       Tuple						):

					"""simple docstring"""






					return (self.num_rows, self.num_columns)







				@property
				def 							__UpperCAmelCase					( self    :       List[str]						):

					"""simple docstring"""






					return self.order[0] == self.order[1]







				def 							__UpperCAmelCase					( self    :       Optional[Any]						):

					"""simple docstring"""






					_lowercase :    Optional[int]							=							[
					    [0 if column_num != row_num else 1 for column_num in range(self.num_rows						)]
					    for row_num in range(self.num_rows						)
					]
					return Matrix(lowerCamelCase_						)







				def 							__UpperCAmelCase					( self    :       Dict						):

					"""simple docstring"""






					if not self.is_square:
						return 0
					if self.order == (0, 0):
						return 1
					if self.order == (1, 1):
						return int(self.rows[0][0]						)
					if self.order == (2, 2):
						return int(
						    (self.rows[0][0] * self.rows[1][1])
						    - (self.rows[0][1] * self.rows[1][0])						)
					else:
						return sum(
						    self.rows[0][column] * self.cofactors().rows[0][column]
						    for column in range(self.num_columns						)						)







				def 							__UpperCAmelCase					( self    :       Union[str, Any]						):

					"""simple docstring"""






					return bool(self.determinant()						)







				def 							__UpperCAmelCase					( self    :       int			,					lowerCamelCase_    :       int			,					lowerCamelCase_    :       int						):

					"""simple docstring"""






					_lowercase :    List[str]							=							[
					    [
					        self.rows[other_row][other_column]
					        for other_column in range(self.num_columns						)
					        if other_column != column
					    ]
					    for other_row in range(self.num_rows						)
					    if other_row != row
					]
					return Matrix(lowerCamelCase_						).determinant()







				def 							__UpperCAmelCase					( self    :       str			,					lowerCamelCase_    :       int			,					lowerCamelCase_    :       int						):

					"""simple docstring"""






					if (row + column) % 2 == 0:
						return self.get_minor(lowerCamelCase_			,					lowerCamelCase_						)
					return -1 * self.get_minor(lowerCamelCase_			,					lowerCamelCase_						)







				def 							__UpperCAmelCase					( self    :       Dict						):

					"""simple docstring"""






					return Matrix(
					    [
					        [self.get_minor(lowerCamelCase_			,					lowerCamelCase_						) for column in range(self.num_columns						)]
					        for row in range(self.num_rows						)
					    ]						)







				def 							__UpperCAmelCase					( self    :       Tuple						):

					"""simple docstring"""






					return Matrix(
					    [
					        [
					            self.minors().rows[row][column]
					            if (row + column) % 2 == 0
					            else self.minors().rows[row][column] * -1
					            for column in range(self.minors().num_columns						)
					        ]
					        for row in range(self.minors().num_rows						)
					    ]						)







				def 							__UpperCAmelCase					( self    :       Tuple						):

					"""simple docstring"""






					_lowercase :    str							=							[
					    [self.cofactors().rows[column][row] for column in range(self.num_columns						)]
					    for row in range(self.num_rows						)
					]
					return Matrix(lowerCamelCase_						)







				def 							__UpperCAmelCase					( self    :       Union[str, Any]						):

					"""simple docstring"""






					_lowercase :    Dict							=							self.determinant()
					if not determinant:
						raise TypeError('Only matrices with a non-zero determinant have an inverse'						)
					return self.adjugate() * (1 / determinant)







				def __repr__( self    :       List[str]						):

					"""simple docstring"""






					return str(self.rows						)







				def __str__( self    :       str						):

					"""simple docstring"""






					if self.num_rows == 0:
						return "[]"
					if self.num_rows == 1:
						return "[[" + ". ".join(str(self.rows[0]						)						) + "]]"
					return (
					    "["
					    + "\n ".join(
					        [
					            '[' + '. '.join([str(lowerCamelCase_						) for value in row]						) + '.]'
					            for row in self.rows
					        ]						)
					    + "]"
					)







				def 							__UpperCAmelCase					( self    :       Union[str, Any]			,					lowerCamelCase_    :       list[int]			,					lowerCamelCase_    :       int | None = None						):

					"""simple docstring"""






					_lowercase :    Union[str, Any]							=							TypeError('Row must be a list containing all ints and/or floats'						)
					if not isinstance(lowerCamelCase_			,					lowerCamelCase_						):
						raise type_error
					for value in row:
						if not isinstance(lowerCamelCase_			,					(int, float)						):
							raise type_error
					if len(lowerCamelCase_						) != self.num_columns:
						raise ValueError(
						    'Row must be equal in length to the other rows in the matrix'						)
					if position is None:
						self.rows.append(lowerCamelCase_						)
					else:
						_lowercase :    Any							=							self.rows[0:position] + [row] + self.rows[position:]







				def 							__UpperCAmelCase					( self    :       str			,					lowerCamelCase_    :       list[int]			,					lowerCamelCase_    :       int | None = None						):

					"""simple docstring"""






					_lowercase :    Tuple							=							TypeError(
					    'Column must be a list containing all ints and/or floats'						)
					if not isinstance(lowerCamelCase_			,					lowerCamelCase_						):
						raise type_error
					for value in column:
						if not isinstance(lowerCamelCase_			,					(int, float)						):
							raise type_error
					if len(lowerCamelCase_						) != self.num_rows:
						raise ValueError(
						    'Column must be equal in length to the other columns in the matrix'						)
					if position is None:
						_lowercase :    List[Any]							=							[self.rows[i] + [column[i]] for i in range(self.num_rows						)]
					else:
						_lowercase :    Any							=							[
						    self.rows[i][0:position] + [column[i]] + self.rows[i][position:]
						    for i in range(self.num_rows						)
						]







				def __eq__( self    :       Union[str, Any]			,					lowerCamelCase_    :       object						):

					"""simple docstring"""






					if not isinstance(lowerCamelCase_			,					lowerCamelCase_						):
						return NotImplemented
					return self.rows == other.rows







				def __ne__( self    :       Any			,					lowerCamelCase_    :       object						):

					"""simple docstring"""






					return not self == other







				def __neg__( self    :       int						):

					"""simple docstring"""






					return self * -1







				def __add__( self    :       Optional[int]			,					lowerCamelCase_    :       Matrix						):

					"""simple docstring"""






					if self.order != other.order:
						raise ValueError('Addition requires matrices of the same order'						)
					return Matrix(
					    [
					        [self.rows[i][j] + other.rows[i][j] for j in range(self.num_columns						)]
					        for i in range(self.num_rows						)
					    ]						)







				def __sub__( self    :       str			,					lowerCamelCase_    :       Matrix						):

					"""simple docstring"""






					if self.order != other.order:
						raise ValueError('Subtraction requires matrices of the same order'						)
					return Matrix(
					    [
					        [self.rows[i][j] - other.rows[i][j] for j in range(self.num_columns						)]
					        for i in range(self.num_rows						)
					    ]						)







				def __mul__( self    :       Optional[Any]			,					lowerCamelCase_    :       Matrix | int | float						):

					"""simple docstring"""






					if isinstance(lowerCamelCase_			,					(int, float)						):
						return Matrix(
						    [[int(element * other						) for element in row] for row in self.rows]						)
					elif isinstance(lowerCamelCase_			,					lowerCamelCase_						):
						if self.num_columns != other.num_rows:
							raise ValueError(
							    'The number of columns in the first matrix must '
							    'be equal to the number of rows in the second'						)
						return Matrix(
						    [
						        [Matrix.dot_product(lowerCamelCase_			,					lowerCamelCase_						) for column in other.columns()]
						        for row in self.rows
						    ]						)
					else:
						raise TypeError(
						    'A Matrix can only be multiplied by an int, float, or another matrix'						)







				def __pow__( self    :       Optional[Any]			,					lowerCamelCase_    :       int						):

					"""simple docstring"""






					if not isinstance(lowerCamelCase_			,					lowerCamelCase_						):
						raise TypeError('A Matrix can only be raised to the power of an int'						)
					if not self.is_square:
						raise ValueError('Only square matrices can be raised to a power'						)
					if other == 0:
						return self.identity()
					if other < 0:
						if self.is_invertable():
							return self.inverse() ** (-other)
						raise ValueError(
						    'Only invertable matrices can be raised to a negative power'						)
					_lowercase :    str							=							self
					for _ in range(other - 1						):
						result *= self
					return result







				@classmethod
				def 							__UpperCAmelCase					( cls    :       str			,					lowerCamelCase_    :       list[int]			,					lowerCamelCase_    :       list[int]						):

					"""simple docstring"""






					return sum(row[i] * column[i] for i in range(len(lowerCamelCase_						)						)						)


if __name__ == "__main__":
						import doctest

						doctest.testmod()



