




"""simple docstring"""






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


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 	_snake_case     (							lowercase__						):
				assert all(row == sorted(lowercase__				,       reverse=lowercase__						) for row in grid						)
				assert all(list(lowercase__						) == sorted(lowercase__				,       reverse=lowercase__						) for col in zip(*lowercase__						)						)







def 	_snake_case     (							lowercase__						):
				_lowerCamelCase	:     str       =       0
				_lowerCamelCase	:     List[str]       =       len(lowercase__						) - 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	:     Any       =       (left + right) // 2
								_lowerCamelCase	:     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	:     Dict       =       mid + 1
								else:
												_lowerCamelCase	:     Optional[int]       =       mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
				return len(lowercase__						)







def 	_snake_case     (							lowercase__						):
				_lowerCamelCase	:     List[Any]       =       0
				_lowerCamelCase	:     List[str]       =       len(grid[0]						)

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







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







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







def 	_snake_case     (							):
				from timeit import timeit

				print('Running benchmarks'						)
				_lowerCamelCase	:     Union[str, Any]       =       (
				    '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	:     Dict       =       timeit(f'''{func}(grid=grid)'''				,       setup=lowercase__				,       number=500						)
								print(f'''{func}() took {time:0.4f} seconds'''						)


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			benchmark()





"""simple docstring"""






from ...configuration_utils import PretrainedConfig
from ...utils import logging


lowercase__			=		logging.get_logger(__name__)

lowercase__			=		{"""openai-gpt""": """https://huggingface.co/openai-gpt/resolve/main/config.json"""}






class lowerCAmelCase__      (	lowercase		):






			'''simple docstring'''



			lowerCamelCase__ =     """openai-gpt"""
			lowerCamelCase__ =     {
			    """max_position_embeddings""": """n_positions""",
			    """hidden_size""": """n_embd""",
			    """num_attention_heads""": """n_head""",
			    """num_hidden_layers""": """n_layer""",
			}
			def __init__(    self    , lowercase=40478    , lowercase=512    , lowercase=768    , lowercase=12    , lowercase=12    , lowercase="gelu"    , lowercase=0.1    , lowercase=0.1    , lowercase=0.1    , lowercase=1E-5    , lowercase=0.02    , lowercase="cls_index"    , lowercase=True    , lowercase=None    , lowercase=True    , lowercase=0.1    , **lowercase    , ):
							_lowerCamelCase	:     Tuple       =       vocab_size
							_lowerCamelCase	:     List[str]       =       n_positions
							_lowerCamelCase	:     Tuple       =       n_embd
							_lowerCamelCase	:     Optional[int]       =       n_layer
							_lowerCamelCase	:     List[Any]       =       n_head
							_lowerCamelCase	:     Dict       =       afn
							_lowerCamelCase	:     Union[str, Any]       =       resid_pdrop
							_lowerCamelCase	:     Dict       =       embd_pdrop
							_lowerCamelCase	:     List[Any]       =       attn_pdrop
							_lowerCamelCase	:     Any       =       layer_norm_epsilon
							_lowerCamelCase	:     List[Any]       =       initializer_range
							_lowerCamelCase	:     List[Any]       =       summary_type
							_lowerCamelCase	:     List[str]       =       summary_use_proj
							_lowerCamelCase	:     Tuple       =       summary_activation
							_lowerCamelCase	:     int       =       summary_first_dropout
							_lowerCamelCase	:     str       =       summary_proj_to_labels
							super().__init__(**lowercase    )