






"""simple docstring"""

def _lowerCAmelCase	(  ):

						'''simple docstring'''






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


lowercase    			=       generate_large_matrix()
lowercase    			=       (
    [[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	(  __lowerCamelCase:list[list[int]]   ):

						'''simple docstring'''






						assert all(row == sorted(__lowerCamelCase ,						reverse=__lowerCamelCase   ) for row in grid   )
						assert all(list(__lowerCamelCase   ) == sorted(__lowerCamelCase ,						reverse=__lowerCamelCase   ) for col in zip(*__lowerCamelCase   )   )






def _lowerCAmelCase	(  __lowerCamelCase:list[int]   ):

						'''simple docstring'''






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






def _lowerCAmelCase	(  __lowerCamelCase:list[list[int]]   ):

						'''simple docstring'''






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

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






def _lowerCAmelCase	(  __lowerCamelCase:list[list[int]]   ):

						'''simple docstring'''






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






def _lowerCAmelCase	(  __lowerCamelCase:list[list[int]]   ):

						'''simple docstring'''






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






def _lowerCAmelCase	(  ):

						'''simple docstring'''






						from timeit import timeit

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


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			benchmark()











"""simple docstring"""

def _lowerCAmelCase	(  __lowerCamelCase:int   ):

						'''simple docstring'''






						__magic_name__            =     n ** (1 / 3)
						return (val * val * val) == n


if __name__ == "__main__":
			print(perfect_cube(27))
			print(perfect_cube(4))



