

"""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_     :			int	  =			generate_large_matrix()
SCREAMING_SNAKE_CASE_     :			Dict	  =			(
    [[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__   )      ->      None:




   """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 	UpperCAmelCase__   (				A__   )      ->      int:




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



def 	UpperCAmelCase__   (				A__   )      ->      int:




   """simple docstring"""
   lowerCamelCase__						=			0
   lowerCamelCase__						=			len(grid[0]   )

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



def 	UpperCAmelCase__   (				A__   )      ->      int:




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



def 	UpperCAmelCase__   (				A__   )      ->      int:




   """simple docstring"""
   lowerCamelCase__						=			0
   for row in grid:
      for i, number in enumerate(A__   ):
         if number < 0:
            total += len(A__   ) - i
            break
   return total



def 	UpperCAmelCase__   (				)      ->      None:




   """simple docstring"""
   from timeit import timeit

   print("Running benchmarks"   )
   lowerCamelCase__						=			(
       "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__						=			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()







"""simple docstring"""




# Algorithm for the pigeonhole sorting





def 	UpperCAmelCase__   (				A__   )      ->      Dict:




   """simple docstring"""
   lowerCamelCase__						=			min(A__   )  # min() finds the minimum value
   lowerCamelCase__						=			max(A__   )  # max() finds the maximum value

   lowerCamelCase__						=			max_val - min_val + 1  # size is difference of max and min values plus one

   # list of pigeonholes of size equal to the variable size
   lowerCamelCase__						=			[0] * size

   # Populate the pigeonholes.
   for x in a:
      assert isinstance(A__	,    A__   ), "integers only please"
      holes[x - min_val] += 1

   # Putting the elements back into the array in an order.
   lowerCamelCase__						=			0
   for count in range(A__   ):
      while holes[count] > 0:
         holes[count] -= 1
         lowerCamelCase__						=			count + min_val
         i += 1



def 	UpperCAmelCase__   (				)      ->      Optional[int]:




   """simple docstring"""
   lowerCamelCase__						=			[8, 3, 2, 7, 4, 6, 8]
   pigeonhole_sort(A__   )
   print("Sorted order is:"	,    " ".join(A__   )   )


if __name__ == "__main__":
     main()




