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


lowerCAmelCase__       = generate_large_matrix()
lowerCAmelCase__       = (
    [[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(	__A			):
  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      _lowerCAmelCase(	__A			):
  UpperCAmelCase					      =  0
  UpperCAmelCase					      =  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:
    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(__A			)
def      _lowerCAmelCase(	__A			):
  UpperCAmelCase					      =  0
  UpperCAmelCase					      =  len(grid[0]			)

  for i in range(len(__A			)			):
    UpperCAmelCase					      =  find_negative_index(grid[i][:bound]			)
    total += bound
  return (len(__A			) * len(grid[0]			)) - total
def      _lowerCAmelCase(	__A			):
  return len([number for row in grid for number in row if number < 0]			)
def      _lowerCAmelCase(	__A			):
  UpperCAmelCase					      =  0
  for row in grid:
    for i, number in enumerate(__A			):
      if number < 0:
        total += len(__A			) - i
        break
  return total
def      _lowerCAmelCase(	):
  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=__A   ,       number=500			)
    print(F"{func}() took {time:0.4f} seconds"			)


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      benchmark()






import unittest

import numpy as np
def      _lowerCAmelCase(	__A   ,       __A   ,       __A   ,       __A = None   ,       ):
  UpperCAmelCase					      =  np.shape(__A			)
  UpperCAmelCase					      =  np.shape(__A			)
  UpperCAmelCase					      =  np.shape(__A			)

  if shape_a[0] != shape_b[0]:
    UpperCAmelCase					      =  (
        "Expected the same number of rows for A and B. "
        F"Instead found A of size {shape_a} and B of size {shape_b}"
    )
    raise ValueError(__A			)

  if shape_b[1] != shape_c[1]:
    UpperCAmelCase					      =  (
        "Expected the same number of columns for B and C. "
        F"Instead found B of size {shape_b} and C of size {shape_c}"
    )
    raise ValueError(__A			)

  UpperCAmelCase					      =  pseudo_inv
  if a_inv is None:
    try:
      UpperCAmelCase					      =  np.linalg.inv(__A			)
    except np.linalg.LinAlgError:
      raise ValueError(
          "Input matrix A is not invertible. Cannot compute Schur complement."			)

  return mat_c - mat_b.T @ a_inv @ mat_b






class 						__magic_name__    (       unittest.TestCase    ):


 def _UpperCamelCase	(						self		: List[str]    )    ->      None:
   UpperCAmelCase					      =  np.array([[1, 2, 1], [2, 1, 2], [3, 2, 4]]    )
   UpperCAmelCase					      =  np.array([[0, 3], [3, 0], [2, 3]]    )
   UpperCAmelCase					      =  np.array([[2, 1], [6, 3]]    )

   UpperCAmelCase					      =  schur_complement(lowerCAmelCase__			,						lowerCAmelCase__			,						lowerCAmelCase__    )

   UpperCAmelCase					      =  np.block([[a, b], [b.T, c]]    )

   UpperCAmelCase					      =  np.linalg.det(lowerCAmelCase__    )
   UpperCAmelCase					      =  np.linalg.det(lowerCAmelCase__    )
   UpperCAmelCase					      =  np.linalg.det(lowerCAmelCase__    )

   self.assertAlmostEqual(lowerCAmelCase__			,						det_a * det_s    )


 def _UpperCamelCase	(						self		: str    )    ->      None:
   UpperCAmelCase					      =  np.array([[1, 2, 1], [2, 1, 2], [3, 2, 4]]    )
   UpperCAmelCase					      =  np.array([[0, 3], [3, 0], [2, 3]]    )
   UpperCAmelCase					      =  np.array([[2, 1], [6, 3]]    )

   with self.assertRaises(lowerCAmelCase__    ):
     schur_complement(lowerCAmelCase__			,						lowerCAmelCase__			,						lowerCAmelCase__    )


 def _UpperCamelCase	(						self		: Dict    )    ->      None:
   UpperCAmelCase					      =  np.array([[1, 2, 1], [2, 1, 2], [3, 2, 4]]    )
   UpperCAmelCase					      =  np.array([[0, 3], [3, 0], [2, 3]]    )
   UpperCAmelCase					      =  np.array([[2, 1, 3], [6, 3, 5]]    )

   with self.assertRaises(lowerCAmelCase__    ):
     schur_complement(lowerCAmelCase__			,						lowerCAmelCase__			,						lowerCAmelCase__    )


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      unittest.main()



