



def        A       (      ):





							'''simple docstring'''




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


_snake_case	=						generate_large_matrix()
_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        A       (      _lowerCamelCase						):





							'''simple docstring'''




							assert all(row == sorted(_lowerCamelCase       ,				reverse=_lowerCamelCase						) for row in grid						)
							assert all(list(_lowerCamelCase						) == sorted(_lowerCamelCase       ,				reverse=_lowerCamelCase						) for col in zip(*_lowerCamelCase						)						)






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




							_lowerCAmelCase  :							Optional[int]				     =					0
							_lowerCAmelCase  :							Any				     =					len(_lowerCamelCase						) - 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  :							List[Any]				     =					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  :							Tuple				     =					mid + 1
														else:
																					_lowerCAmelCase  :							int				     =					mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
							return len(_lowerCamelCase						)






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




							_lowerCAmelCase  :							Tuple				     =					0
							_lowerCAmelCase  :							str				     =					len(grid[0]						)

							for i in range(len(_lowerCamelCase						)						):
														_lowerCAmelCase  :							Any				     =					find_negative_index(grid[i][:bound]						)
														total += bound
							return (len(_lowerCamelCase						) * len(grid[0]						)) - total






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




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






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




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






def        A       (      ):





							'''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  :							Dict				     =					timeit(F"{func}(grid=grid)"       ,				setup=_lowerCamelCase       ,				number=500						)
														print(F"{func}() took {time:0.4f} seconds"						)


if __name__ == "__main__":
						import doctest

						doctest.testmod()
						benchmark()





from __future__ import annotations






def        A       (      _lowerCamelCase						):





							'''simple docstring'''




							if not nums:
														raise ValueError("List is empty"						)
							return sum(_lowerCamelCase						) / len(_lowerCamelCase						)


if __name__ == "__main__":
						import doctest

						doctest.testmod()
