

'''simple docstring'''
def        _lowerCAmelCase					(						)      ->			list[list[int]]:
     """simple docstring"""




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


lowerCamelCase :      Optional[Any]					 =     generate_large_matrix()
lowerCamelCase :      Optional[int]					 =     (
    [[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						:     list[list[int]]				)      ->			None:
     """simple docstring"""




     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						:     list[int]				)      ->			int:
     """simple docstring"""




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


def        _lowerCAmelCase					(						_UpperCamelCase						:     list[list[int]]				)      ->			int:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =0
     _SCREAMING_SNAKE_CASE							    =len(grid[0]				)

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


def        _lowerCAmelCase					(						_UpperCamelCase						:     list[list[int]]				)      ->			int:
     """simple docstring"""




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


def        _lowerCAmelCase					(						_UpperCamelCase						:     list[list[int]]				)      ->			int:
     """simple docstring"""




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


def        _lowerCAmelCase					(						)      ->			None:
     """simple docstring"""




     from timeit import timeit

     print('Running benchmarks'				)
     _SCREAMING_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
     ):
          _SCREAMING_SNAKE_CASE							    =timeit(f"{func}(grid=grid)"							, setup=_UpperCamelCase							, number=5_00				)
          print(f"{func}() took {time:0.4f} seconds"				)


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     benchmark()



'''simple docstring'''
lowerCamelCase :      Any					 =     "\n# Transformers installation\n! pip install transformers datasets\n# To install from source instead of the last release, comment the command above and uncomment the following one.\n# ! pip install git+https://github.com/huggingface/transformers.git\n"

lowerCamelCase :      int					 =     [{"type": "code", "content": INSTALL_CONTENT}]
lowerCamelCase :      str					 =     {
    "{processor_class}": "FakeProcessorClass",
    "{model_class}": "FakeModelClass",
    "{object_class}": "FakeObjectClass",
}
