
"""simple docstring"""







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


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    (_UpperCamelCase		):
	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		):
	__lowerCAmelCase      :						List[str]						      =				0
	__lowerCAmelCase      :						Tuple						      =				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      :						Any						      =				(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      :						Tuple						      =				mid + 1
		else:
			__lowerCAmelCase      :						Dict						      =				mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
	return len(_UpperCamelCase		)
def    __lowerCAmelCase    (_UpperCamelCase		):
	__lowerCAmelCase      :						Union[str, Any]						      =				0
	__lowerCAmelCase      :						Tuple						      =				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    __lowerCAmelCase    (_UpperCamelCase		):
	return len([number for row in grid for number in row if number < 0]		)
def    __lowerCAmelCase    (_UpperCamelCase		):
	__lowerCAmelCase      :						str						      =				0
	for row in grid:
		for i, number in enumerate(_UpperCamelCase		):
			if number < 0:
				total += len(_UpperCamelCase		) - i
				break
	return total
def    __lowerCAmelCase    ():
	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      :						List[str]						      =				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
def    __lowerCAmelCase    (_UpperCamelCase		):
	__lowerCAmelCase      :						List[str]						      =				str(_UpperCamelCase		)
	return len(_UpperCamelCase		) == 9 and set(_UpperCamelCase		) == set('123456789'		)
def    __lowerCAmelCase    ():
	for base_num in range(9999	,  4999	,  -1		):
		__lowerCAmelCase      :						Union[str, Any]						      =				10_0002 * base_num
		if is_9_pandigital(_UpperCamelCase		):
			return candidate

	for base_num in range(333	,  99	,  -1		):
		__lowerCAmelCase      :						Dict						      =				100_2003 * base_num
		if is_9_pandigital(_UpperCamelCase		):
			return candidate

	return None


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