



"""simple docstring"""






from __future__ import annotations

from collections.abc import Iterator
from typing import Any

class        __SCREAMING_SNAKE_CASE	:


					'''simple docstring'''





					def __init__(       self							:  List[Any],  lowerCamelCase							:  Any     )->					Tuple:
								lowerCamelCase__		:		Any			=data
								lowerCamelCase__		:		Node | None			=None





class        __SCREAMING_SNAKE_CASE	:


					'''simple docstring'''





					def __init__(       self							:  Tuple     )->					List[Any]:
								lowerCamelCase__		:		Optional[Any]			=None
								lowerCamelCase__		:		Dict			=None



					def __iter__(       self							:  Dict     )->					Iterator[Any]:
								lowerCamelCase__		:		int			=self.head
								while self.head:
											yield node.data
											lowerCamelCase__		:		Optional[Any]			=node.next
											if node == self.head:
														break



					def __len__(       self							:  Optional[int]     )->					int:
								return sum(1 for _ in self     )



					def __repr__(       self							:  int     )->					Union[str, Any]:
								return "->".join(str(lowerCamelCase     ) for item in iter(self     )     )



					def 		snake_case       (       self							:  Union[str, Any],  lowerCamelCase							:  Any     )->					None:
								self.insert_nth(len(self     ),  lowerCamelCase     )



					def 		snake_case       (       self							:  List[Any],  lowerCamelCase							:  Any     )->					None:
								self.insert_nth(0,  lowerCamelCase     )



					def 		snake_case       (       self							:  int,  lowerCamelCase							:  int,  lowerCamelCase							:  Any     )->					None:
								if index < 0 or index > len(self     ):
											raise IndexError('''list index out of range.'''     )
								lowerCamelCase__		:		Dict			=Node(lowerCamelCase     )
								if self.head is None:
											lowerCamelCase__		:		Optional[Any]			=new_node  # first node points itself
											lowerCamelCase__		:		Union[str, Any]			=new_node
								elif index == 0:  # insert at head
											lowerCamelCase__		:		Tuple			=self.head
											lowerCamelCase__		:		str			=new_node
								else:
											lowerCamelCase__		:		List[str]			=self.head
											for _ in range(index - 1     ):
														lowerCamelCase__		:		str			=temp.next
											lowerCamelCase__		:		str			=temp.next
											lowerCamelCase__		:		Optional[int]			=new_node
											if index == len(self     ) - 1:  # insert at tail
														lowerCamelCase__		:		int			=new_node



					def 		snake_case       (       self							:  str     )->					List[str]:
								return self.delete_nth(0     )



					def 		snake_case       (       self							:  Union[str, Any]     )->					Any:
								return self.delete_nth(len(self     ) - 1     )



					def 		snake_case       (       self							:  Tuple,  lowerCamelCase							:  int = 0     )->					Any:
								if not 0 <= index < len(self     ):
											raise IndexError('''list index out of range.'''     )
								lowerCamelCase__		:		List[str]			=self.head
								if self.head == self.tail:  # just one node
											lowerCamelCase__		:		Optional[Any]			=None
								elif index == 0:  # delete head node
											lowerCamelCase__		:		Dict			=self.tail.next.next
											lowerCamelCase__		:		Optional[int]			=self.head.next
								else:
											lowerCamelCase__		:		Any			=self.head
											for _ in range(index - 1     ):
														lowerCamelCase__		:		Any			=temp.next
											lowerCamelCase__		:		List[str]			=temp.next
											lowerCamelCase__		:		str			=temp.next.next
											if index == len(self     ) - 1:  # delete at tail
														lowerCamelCase__		:		Optional[int]			=temp
								return delete_node.data




					def 		snake_case       (       self							:  Any     )->					bool:
								return len(self     ) == 0






def      snake_case__   (		):
			"""simple docstring"""
			lowerCamelCase__		:		List[str]			=CircularLinkedList()
			assert len(__lowerCamelCase	) == 0
			assert circular_linked_list.is_empty() is True
			assert str(__lowerCamelCase	) == ""

			try:
						circular_linked_list.delete_front()
						raise AssertionError  # This should not happen
			except IndexError:
						assert True  # This should happen

			try:
						circular_linked_list.delete_tail()
						raise AssertionError  # This should not happen
			except IndexError:
						assert True  # This should happen

			try:
						circular_linked_list.delete_nth(-1	)
						raise AssertionError
			except IndexError:
						assert True

			try:
						circular_linked_list.delete_nth(0	)
						raise AssertionError
			except IndexError:
						assert True

			assert circular_linked_list.is_empty() is True
			for i in range(5	):
						assert len(__lowerCamelCase	) == i
						circular_linked_list.insert_nth(__lowerCamelCase							,		i + 1	)
			assert str(__lowerCamelCase	) == "->".join(str(__lowerCamelCase	) for i in range(1							,		6	)	)

			circular_linked_list.insert_tail(6	)
			assert str(__lowerCamelCase	) == "->".join(str(__lowerCamelCase	) for i in range(1							,		7	)	)
			circular_linked_list.insert_head(0	)
			assert str(__lowerCamelCase	) == "->".join(str(__lowerCamelCase	) for i in range(0							,		7	)	)

			assert circular_linked_list.delete_front() == 0
			assert circular_linked_list.delete_tail() == 6
			assert str(__lowerCamelCase	) == "->".join(str(__lowerCamelCase	) for i in range(1							,		6	)	)
			assert circular_linked_list.delete_nth(2	) == 3

			circular_linked_list.insert_nth(2							,		3	)
			assert str(__lowerCamelCase	) == "->".join(str(__lowerCamelCase	) for i in range(1							,		6	)	)

			assert circular_linked_list.is_empty() is False


if __name__ == "__main__":
		import doctest

		doctest.testmod()









"""simple docstring"""






def      snake_case__   (		):
			"""simple docstring"""
			return [list(range(1000 - i							,		-1000 - i							,		-1	)	) for i in range(1000	)]


_lowercase : str      						=						generate_large_matrix()
_lowercase : str      						=						(
    [[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      snake_case__   (		__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      snake_case__   (		__lowerCamelCase				:    list[int]	):
			"""simple docstring"""
			lowerCamelCase__		:		int			=0
			lowerCamelCase__		:		Optional[int]			=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:
						lowerCamelCase__		:		List[str]			=(left + right) // 2
						lowerCamelCase__		:		Union[str, Any]			=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__		:		Union[str, Any]			=mid + 1
						else:
									lowerCamelCase__		:		Dict			=mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
			return len(__lowerCamelCase	)






def      snake_case__   (		__lowerCamelCase				:    list[list[int]]	):
			"""simple docstring"""
			lowerCamelCase__		:		Union[str, Any]			=0
			lowerCamelCase__		:		str			=len(grid[0]	)

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






def      snake_case__   (		__lowerCamelCase				:    list[list[int]]	):
			"""simple docstring"""
			return len([number for row in grid for number in row if number < 0]	)






def      snake_case__   (		__lowerCamelCase				:    list[list[int]]	):
			"""simple docstring"""
			lowerCamelCase__		:		Tuple			=0
			for row in grid:
						for i, number in enumerate(__lowerCamelCase	):
									if number < 0:
												total += len(__lowerCamelCase	) - i
												break
			return total






def      snake_case__   (		):
			"""simple docstring"""
			from timeit import timeit

			print('''Running benchmarks'''	)
			lowerCamelCase__		:		List[str]			=(
			    '''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__		:		Union[str, Any]			=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()




