


def 	_lowerCAmelCase       (    ):


						'''simple docstring'''






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


A							:					Optional[Any]     						=     generate_large_matrix()
A							:					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 	_lowerCAmelCase       (    _lowerCAmelCase ):


						'''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 ):


						'''simple docstring'''






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





def 	_lowerCAmelCase       (    _lowerCAmelCase ):


						'''simple docstring'''






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

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





def 	_lowerCAmelCase       (    _lowerCAmelCase ):


						'''simple docstring'''






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





def 	_lowerCAmelCase       (    _lowerCAmelCase ):


						'''simple docstring'''






						__snake_case				=		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" )
						__snake_case				=		(
						    "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
						):
												__snake_case				=		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()









import itertools
import string
from collections.abc import Generator, Iterable





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	Generator[tuple[str, ...], None, None]:


						'''simple docstring'''






						__snake_case				=		iter(_lowerCAmelCase )
						while True:
												__snake_case				=		tuple(itertools.islice(_lowerCAmelCase      ,	_lowerCAmelCase ) )
												if not chunk:
																		return
												yield chunk





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	str:


						'''simple docstring'''






						__snake_case				=		"".join([c.upper() for c in dirty if c in string.ascii_letters] )
						__snake_case				=		""

						if len(_lowerCAmelCase ) < 2:
												return dirty

						for i in range(len(_lowerCAmelCase ) - 1 ):
												clean += dirty[i]

												if dirty[i] == dirty[i + 1]:
																		clean += "X"

						clean += dirty[-1]

						if len(_lowerCAmelCase ) & 1:
												clean += "X"

						return clean





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	list[str]:


						'''simple docstring'''






						__snake_case				=		"ABCDEFGHIKLMNOPQRSTUVWXYZ"
						# we're using a list instead of a '2d' array because it makes the math
						# for setting up the table and doing the actual encoding/decoding simpler
						__snake_case				=		[]

						# copy key chars into the table if they are in `alphabet` ignoring duplicates
						for char in key.upper():
												if char not in table and char in alphabet:
																		table.append(_lowerCAmelCase )

    # fill the rest of the table in with the remaining alphabet chars
						for char in alphabet:
												if char not in table:
																		table.append(_lowerCAmelCase )

						return table





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	str:


						'''simple docstring'''






						__snake_case				=		generate_table(_lowerCAmelCase )
						__snake_case				=		prepare_input(_lowerCAmelCase )
						__snake_case				=		""

						# https://en.wikipedia.org/wiki/Playfair_cipher#Description
						for chara, chara in chunker(_lowerCAmelCase      ,	2 ):
												__snake_case		,					__snake_case				=		divmod(table.index(_lowerCAmelCase )      ,	5 )
												__snake_case		,					__snake_case				=		divmod(table.index(_lowerCAmelCase )      ,	5 )

												if rowa == rowa:
																		ciphertext += table[rowa * 5 + (cola + 1) % 5]
																		ciphertext += table[rowa * 5 + (cola + 1) % 5]
												elif cola == cola:
																		ciphertext += table[((rowa + 1) % 5) * 5 + cola]
																		ciphertext += table[((rowa + 1) % 5) * 5 + cola]
												else:  # rectangle
																		ciphertext += table[rowa * 5 + cola]
																		ciphertext += table[rowa * 5 + cola]

						return ciphertext





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	str:


						'''simple docstring'''






						__snake_case				=		generate_table(_lowerCAmelCase )
						__snake_case				=		""

						# https://en.wikipedia.org/wiki/Playfair_cipher#Description
						for chara, chara in chunker(_lowerCAmelCase      ,	2 ):
												__snake_case		,					__snake_case				=		divmod(table.index(_lowerCAmelCase )      ,	5 )
												__snake_case		,					__snake_case				=		divmod(table.index(_lowerCAmelCase )      ,	5 )

												if rowa == rowa:
																		plaintext += table[rowa * 5 + (cola - 1) % 5]
																		plaintext += table[rowa * 5 + (cola - 1) % 5]
												elif cola == cola:
																		plaintext += table[((rowa - 1) % 5) * 5 + cola]
																		plaintext += table[((rowa - 1) % 5) * 5 + cola]
												else:  # rectangle
																		plaintext += table[rowa * 5 + cola]
																		plaintext += table[rowa * 5 + cola]

						return plaintext





