


'''simple docstring'''







def 			lowercase				()     ->   List[Any]:







       """simple docstring"""







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


lowerCAmelCase    :     Union[str, Any]					=						generate_large_matrix()
lowerCAmelCase    :     Any					=						(
    [[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 			lowercase				(_A					)     ->   Dict:







       """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 			lowercase				(_A					)     ->   Union[str, Any]:







       """simple docstring"""







       _lowerCAmelCase    :							str   			=       0
       _lowerCAmelCase    :							Dict   			=       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    :							int   			=       (left + right) // 2
              _lowerCAmelCase    :							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    :							int   			=       mid + 1
              else:
                     _lowerCAmelCase    :							str   			=       mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
       return len(_A					)






def 			lowercase				(_A					)     ->   Optional[Any]:







       """simple docstring"""







       _lowerCAmelCase    :							Optional[Any]   			=       0
       _lowerCAmelCase    :							List[str]   			=       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 			lowercase				(_A					)     ->   Dict:







       """simple docstring"""







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






def 			lowercase				(_A					)     ->   Dict:







       """simple docstring"""







       _lowerCAmelCase    :							int   			=       0
       for row in grid:
              for i, number in enumerate(_A					):
                     if number < 0:
                            total += len(_A					) - i
                            break
       return total






def 			lowercase				()     ->   Dict:







       """simple docstring"""







       from timeit import timeit

       print('Running benchmarks'					)
       _lowerCAmelCase    :							Optional[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    :							Any   			=       timeit(f'{func}(grid=grid)'   ,						setup=_A   ,						number=5_0_0					)
              print(f'{func}() took {time:0.4f} seconds'					)


if __name__ == "__main__":
       import doctest

       doctest.testmod()
       benchmark()





'''simple docstring'''







import pytest

import datasets


# Import fixture modules as plugins
lowerCAmelCase    :     List[str]					=						["""tests.fixtures.files""", """tests.fixtures.hub""", """tests.fixtures.fsspec"""]






def 			lowercase				(_A   ,						_A					):







       """simple docstring"""







       for item in items:
              if any(marker in item.keywords for marker in ['integration', 'unit']					):
                     continue
              item.add_marker(pytest.mark.unit					)






def 			lowercase				(_A					):







       """simple docstring"""







       config.addinivalue_line('markers'   ,						'torchaudio_latest: mark test to run with torchaudio>=0.12'					)






@pytest.fixture(autouse=_A					)
def 			lowercase				(_A   ,						_A					):







       """simple docstring"""







       _lowerCAmelCase    :							str   			=       tmp_path_factory.getbasetemp() / 'cache'
       _lowerCAmelCase    :							Dict   			=       test_hf_cache_home / 'datasets'
       _lowerCAmelCase    :							List[Any]   			=       test_hf_cache_home / 'metrics'
       _lowerCAmelCase    :							List[Any]   			=       test_hf_cache_home / 'modules'
       monkeypatch.setattr('datasets.config.HF_DATASETS_CACHE'   ,						str(_A					)					)
       monkeypatch.setattr('datasets.config.HF_METRICS_CACHE'   ,						str(_A					)					)
       monkeypatch.setattr('datasets.config.HF_MODULES_CACHE'   ,						str(_A					)					)
       _lowerCAmelCase    :							Dict   			=       test_hf_datasets_cache / 'downloads'
       monkeypatch.setattr('datasets.config.DOWNLOADED_DATASETS_PATH'   ,						str(_A					)					)
       _lowerCAmelCase    :							Union[str, Any]   			=       test_hf_datasets_cache / 'downloads' / 'extracted'
       monkeypatch.setattr('datasets.config.EXTRACTED_DATASETS_PATH'   ,						str(_A					)					)






@pytest.fixture(autouse=_A   ,						scope='session'					)
def 			lowercase				():







       """simple docstring"""







       datasets.disable_progress_bar()






@pytest.fixture(autouse=_A					)
def 			lowercase				(_A					):







       """simple docstring"""







       monkeypatch.setattr('datasets.config.HF_UPDATE_DOWNLOAD_COUNTS'   ,						_A					)






@pytest.fixture
def 			lowercase				(_A					):







       """simple docstring"""







       monkeypatch.setattr('sqlalchemy.util.deprecations.SILENCE_UBER_WARNING'   ,						_A					)

