

# Lint as: python3
import dataclasses
import re
from dataclasses import dataclass
from functools import total_ordering
from typing import Optional, Union


lowerCAmelCase							:  List[Any]   	=						re.compile(R"""^(?P<major>\d+)""" R"""\.(?P<minor>\d+)""" R"""\.(?P<patch>\d+)$""")



@total_ordering
@dataclass
class   __lowercase				:




			"""simple docstring"""







			_UpperCAmelCase   :							str
			_UpperCAmelCase   :							Optional[str]										=     None
			_UpperCAmelCase   :							Optional[Union[str, int]]										=     None
			_UpperCAmelCase   :							Optional[Union[str, int]]										=     None
			_UpperCAmelCase   :							Optional[Union[str, int]]										=     None



			def        _SCREAMING_SNAKE_CASE			( self  :     List[str]):
									SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_: Tuple  		=       _str_to_version_tuple(self.version_str)



			def __repr__( self  :     List[Any]):
									return F"{self.tuple[0]}.{self.tuple[1]}.{self.tuple[2]}"



			@property
			def        _SCREAMING_SNAKE_CASE			( self  :     Tuple):
									return self.major, self.minor, self.patch



			def        _SCREAMING_SNAKE_CASE			( self  :     str   ,						lowerCAmelCase__  :     Union[str, Any]):
									if isinstance(lowerCAmelCase__   ,						lowerCAmelCase__):
															return Version(lowerCAmelCase__)
									elif isinstance(lowerCAmelCase__   ,						lowerCAmelCase__):
															return other
									raise TypeError(F"{other} (type {type(lowerCAmelCase__)}) cannot be compared to version.")



			def __eq__( self  :     Tuple   ,						lowerCAmelCase__  :     Optional[int]):
									try:
															SCREAMING_SNAKE_CASE_: List[str]  		=       self._validate_operand(lowerCAmelCase__)
									except (TypeError, ValueError):
															return False
									else:
															return self.tuple == other.tuple



			def __lt__( self  :     Optional[Any]   ,						lowerCAmelCase__  :     Dict):
									SCREAMING_SNAKE_CASE_: Any  		=       self._validate_operand(lowerCAmelCase__)
									return self.tuple < other.tuple



			def __hash__( self  :     str):
									return hash(_version_tuple_to_str(self.tuple))



			@classmethod
			def        _SCREAMING_SNAKE_CASE			( cls  :     List[Any]   ,						lowerCAmelCase__  :     List[Any]):
									SCREAMING_SNAKE_CASE_: Optional[int]  		=       {f.name for f in dataclasses.fields(cls)}
									return cls(**{k: v for k, v in dic.items() if k in field_names})




			def        _SCREAMING_SNAKE_CASE			( self  :     Dict):
									return self.version_str







def 			A_      (    _UpperCAmelCase    ):
						SCREAMING_SNAKE_CASE_: str  		=       _VERSION_REG.match(_UpperCAmelCase    )
						if not res:
												raise ValueError(f"Invalid version '{version_str}'. Format should be x.y.z with {{x,y,z}} being digits."    )
						return tuple(int(_UpperCAmelCase    ) for v in [res.group("major"    ), res.group("minor"    ), res.group("patch"    )]    )







def 			A_      (    _UpperCAmelCase    ):
						return ".".join(str(_UpperCAmelCase    ) for v in version_tuple    )










'''simple docstring'''


def        __lowerCAmelCase       ():
		return [list(range(1_000 - i					,       -1_000 - i					,       -1      )      ) for i in range(1_000      )]


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       (__lowerCAmelCase      ):
		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      ):
		_UpperCAmelCase						:				Any	    =					0
		_UpperCAmelCase						:				str	    =					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:
				_UpperCAmelCase						:				Union[str, Any]	    =					(left + right) // 2
				_UpperCAmelCase						:				List[str]	    =					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						:				Tuple	    =					mid + 1
				else:
						_UpperCAmelCase						:				Optional[Any]	    =					mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
		return len(__lowerCAmelCase      )






def        __lowerCAmelCase       (__lowerCAmelCase      ):
		_UpperCAmelCase						:				str	    =					0
		_UpperCAmelCase						:				int	    =					len(grid[0]      )

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






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






def        __lowerCAmelCase       (__lowerCAmelCase      ):
		_UpperCAmelCase						:				Tuple	    =					0
		for row in grid:
				for i, number in enumerate(__lowerCAmelCase      ):
						if number < 0:
								total += len(__lowerCAmelCase      ) - i
								break
		return total






def        __lowerCAmelCase       ():
		from timeit import timeit

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


if __name__ == "__main__":
						import doctest

						doctest.testmod()
						benchmark()



