






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


a__       =     generate_large_matrix()
a__       =     (
    [[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 _UpperCAmelCase   (	a						:	list[list[int]] ):
							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 _UpperCAmelCase   (	a						:	list[int] ):
							snake_case__	  =       0
							snake_case__	  =       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:
														snake_case__	  =       (left + right) // 2
														snake_case__	  =       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:
																					snake_case__	  =       mid + 1
														else:
																					snake_case__	  =       mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
							return len(a )

def _UpperCAmelCase   (	a						:	list[list[int]] ):
							snake_case__	  =       0
							snake_case__	  =       len(grid[0] )

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

def _UpperCAmelCase   (	a						:	list[list[int]] ):
							return len([number for row in grid for number in row if number < 0] )

def _UpperCAmelCase   (	a						:	list[list[int]] ):
							snake_case__	  =       0
							for row in grid:
														for i, number in enumerate(a ):
																					if number < 0:
																												total += len(a ) - i
																												break
							return total

def _UpperCAmelCase   (	):
							from timeit import timeit

							print("""Running benchmarks""" )
							snake_case__	  =       (
							    """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
							):
														snake_case__	  =       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 typing import TYPE_CHECKING

# rely on isort to merge the imports
from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


a__       =     {
    """configuration_autoformer""": [
        """AUTOFORMER_PRETRAINED_CONFIG_ARCHIVE_MAP""",
        """AutoformerConfig""",
    ],
}

try:
	if not is_torch_available():
		raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
	pass
else:
	a__       =     [
	    """AUTOFORMER_PRETRAINED_MODEL_ARCHIVE_LIST""",
	    """AutoformerForPrediction""",
	    """AutoformerModel""",
	    """AutoformerPreTrainedModel""",
	]


if TYPE_CHECKING:
	from .configuration_autoformer import (
	    AUTOFORMER_PRETRAINED_CONFIG_ARCHIVE_MAP,
	    AutoformerConfig,
	)

	try:
		if not is_torch_available():
			raise OptionalDependencyNotAvailable()
	except OptionalDependencyNotAvailable:
		pass
	else:
		from .modeling_autoformer import (
		    AUTOFORMER_PRETRAINED_MODEL_ARCHIVE_LIST,
		    AutoformerForPrediction,
		    AutoformerModel,
		    AutoformerPreTrainedModel,
		)

else:
	import sys

	a__       =     _LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)
