





'''simple docstring'''




def 	UpperCAmelCase_							(					)		->       list[list[int]]:


     '''simple docstring'''



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


__SCREAMING_SNAKE_CASE     :str       =				generate_large_matrix()
__SCREAMING_SNAKE_CASE     :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 	UpperCAmelCase_							(					__lowercase							:      list[list[int]]       )		->       None:


     '''simple docstring'''



     assert all(row == sorted(__lowercase			,     reverse=__lowercase       ) for row in grid       )
     assert all(list(__lowercase       ) == sorted(__lowercase			,     reverse=__lowercase       ) for col in zip(*__lowercase       )       )
def 	UpperCAmelCase_							(					__lowercase							:      list[int]       )		->       int:


     '''simple docstring'''



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


     '''simple docstring'''



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

     for i in range(len(__lowercase       )       ):
          _UpperCAmelCase     							=   find_negative_index(grid[i][:bound]       )
          total += bound
     return (len(__lowercase       ) * len(grid[0]       )) - total
def 	UpperCAmelCase_							(					__lowercase							:      list[list[int]]       )		->       int:


     '''simple docstring'''



     return len([number for row in grid for number in row if number < 0]       )
def 	UpperCAmelCase_							(					__lowercase							:      list[list[int]]       )		->       int:


     '''simple docstring'''



     _UpperCAmelCase     							=   0
     for row in grid:
          for i, number in enumerate(__lowercase       ):
               if number < 0:
                    total += len(__lowercase       ) - i
                    break
     return total
def 	UpperCAmelCase_							(					)		->       None:


     '''simple docstring'''



     from timeit import timeit

     print("Running benchmarks"       )
     _UpperCAmelCase     							=   (
         "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
     ):
          _UpperCAmelCase     							=   timeit(f'{func}(grid=grid)'			,     setup=__lowercase			,     number=500       )
          print(f'{func}() took {time:0.4f} seconds'       )


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  benchmark()








"""simple docstring"""







lowerCAmelCase__      				=   [
    '''Audio''',
    '''Array2D''',
    '''Array3D''',
    '''Array4D''',
    '''Array5D''',
    '''ClassLabel''',
    '''Features''',
    '''Sequence''',
    '''Value''',
    '''Image''',
    '''Translation''',
    '''TranslationVariableLanguages''',
]
from .audio import Audio
from .features import ArrayaD, ArrayaD, ArrayaD, ArrayaD, ClassLabel, Features, Sequence, Value
from .image import Image
from .translation import Translation, TranslationVariableLanguages





