


def 					lowerCamelCase_   (	):




		"""simple docstring"""






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


lowerCamelCase						=		generate_large_matrix()
lowerCamelCase						=		(
    [[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_   (	_a	):




		"""simple docstring"""






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






def 					lowerCamelCase_   (	_a	):




		"""simple docstring"""






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






def 					lowerCamelCase_   (	_a	):




		"""simple docstring"""






		lowerCAmelCase__       :      Dict   					= 0
		lowerCAmelCase__       :      Tuple   					= len(grid[0]	)

		for i in range(len(_a	)	):
				lowerCAmelCase__       :      Union[str, Any]   					= find_negative_index(grid[i][:bound]	)
				total += bound
		return (len(_a	) * len(grid[0]	)) - total






def 					lowerCamelCase_   (	_a	):




		"""simple docstring"""






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






def 					lowerCamelCase_   (	_a	):




		"""simple docstring"""






		lowerCAmelCase__       :      Union[str, Any]   					= 0
		for row in grid:
				for i, number in enumerate(_a	):
						if number < 0:
								total += len(_a	) - i
								break
		return total






def 					lowerCamelCase_   (	):




		"""simple docstring"""






		from timeit import timeit

		print('''Running benchmarks'''	)
		lowerCAmelCase__       :      Union[str, 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[int]   					= timeit(f'{func}(grid=grid)'     ,       setup=_a     ,       number=500	)
				print(f'{func}() took {time:0.4f} seconds'	)


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		benchmark()








from __future__ import annotations






def 					lowerCamelCase_   (	_a     ,       _a     ,       _a     ,       _a	):  # noqa: E741




		"""simple docstring"""






		while r - l > 1:
				lowerCAmelCase__       :      Any   					= (l + r) // 2
				if v[m] >= key:
						lowerCAmelCase__       :      int   					= m
				else:
						lowerCAmelCase__       :      Tuple   					= m  # noqa: E741
		return r






def 					lowerCamelCase_   (	_a	):




		"""simple docstring"""






		if len(_a	) == 0:
				return 0

		lowerCAmelCase__       :      Optional[int]   					= [0] * len(_a	)
		lowerCAmelCase__       :      List[Any]   					= 1

		lowerCAmelCase__       :      int   					= v[0]

		for i in range(1     ,       len(_a	)	):
				if v[i] < tail[0]:
						lowerCAmelCase__       :      str   					= v[i]
				elif v[i] > tail[length - 1]:
						lowerCAmelCase__       :      Any   					= v[i]
						length += 1
				else:
						lowerCAmelCase__       :      int   					= v[i]

		return length


if __name__ == "__main__":
		import doctest

		doctest.testmod()




