



"""simple docstring"""






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


_lowercase			:			List[Any]										=						generate_large_matrix()
_lowercase			:			int										=						(
    [[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__		:		Union[str, Any]		     =(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__		:		Any		     =mid + 1
						else:
									lowerCamelCase__		:		str		     =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__		:		Dict		     =0
			lowerCamelCase__		:		str		     =len(grid[0]     )

			for i in range(len(__lowerCamelCase     )     ):
						lowerCamelCase__		:		Tuple		     =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__		:		Optional[int]		     =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__		:		Optional[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__		:		List[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()









"""simple docstring"""






from collections import OrderedDict
from typing import Any, Mapping, Optional

from ... import PreTrainedTokenizer
from ...configuration_utils import PretrainedConfig
from ...file_utils import TensorType, is_torch_available
from ...onnx import OnnxConfig, OnnxConfigWithPast, OnnxSeqaSeqConfigWithPast
from ...onnx.utils import compute_effective_axis_dimension
from ...utils import logging


_lowercase			:			Dict										=						logging.get_logger(__name__)

_lowercase			:			int										=						{
    "facebook/blenderbot_small-90M": "https://huggingface.co/facebook/blenderbot_small-90M/resolve/main/config.json",
    # See all BlenderbotSmall models at https://huggingface.co/models?filter=blenderbot_small
}

class 	__SCREAMING_SNAKE_CASE     (				lowerCAmelCase_       ):


					'''simple docstring'''





					_a             =							'blenderbot-small'
					_a             =							['past_key_values']
					_a             =							{'num_attention_heads': 'encoder_attention_heads', 'hidden_size': 'd_model'}



					def __init__(	self							:  Tuple,  lowerCamelCase							:  Any=5_0265,  lowerCamelCase							:  Optional[Any]=512,  lowerCamelCase							:  Union[str, Any]=8,  lowerCamelCase							:  Dict=2048,  lowerCamelCase							:  str=16,  lowerCamelCase							:  List[Any]=8,  lowerCamelCase							:  List[str]=2048,  lowerCamelCase							:  int=16,  lowerCamelCase							:  Any=0.0,  lowerCamelCase							:  Dict=0.0,  lowerCamelCase							:  Tuple=True,  lowerCamelCase							:  Tuple=True,  lowerCamelCase							:  Optional[int]="gelu",  lowerCamelCase							:  Tuple=512,  lowerCamelCase							:  Tuple=0.1,  lowerCamelCase							:  Optional[int]=0.0,  lowerCamelCase							:  Optional[int]=0.0,  lowerCamelCase							:  List[str]=0.02,  lowerCamelCase							:  Any=1,  lowerCamelCase							:  Union[str, Any]=False,  lowerCamelCase							:  Any=0,  lowerCamelCase							:  Tuple=1,  lowerCamelCase							:  Tuple=2,  lowerCamelCase							:  Dict=2,  **lowerCamelCase							:  Any,  )-> Dict:
								lowerCamelCase__		:		Dict		     =vocab_size
								lowerCamelCase__		:		Dict		     =max_position_embeddings
								lowerCamelCase__		:		Optional[Any]		     =d_model
								lowerCamelCase__		:		Union[str, Any]		     =encoder_ffn_dim
								lowerCamelCase__		:		Optional[Any]		     =encoder_layers
								lowerCamelCase__		:		Any		     =encoder_attention_heads
								lowerCamelCase__		:		Union[str, Any]		     =decoder_ffn_dim
								lowerCamelCase__		:		Optional[int]		     =decoder_layers
								lowerCamelCase__		:		Any		     =decoder_attention_heads
								lowerCamelCase__		:		Optional[int]		     =dropout
								lowerCamelCase__		:		str		     =attention_dropout
								lowerCamelCase__		:		Union[str, Any]		     =activation_dropout
								lowerCamelCase__		:		Tuple		     =activation_function
								lowerCamelCase__		:		str		     =init_std
								lowerCamelCase__		:		List[Any]		     =encoder_layerdrop
								lowerCamelCase__		:		List[str]		     =decoder_layerdrop
								lowerCamelCase__		:		Tuple		     =use_cache
								lowerCamelCase__		:		Optional[Any]		     =encoder_layers
								lowerCamelCase__		:		List[Any]		     =scale_embedding  # scale factor will be sqrt(d_model) if True

								super().__init__(
								    pad_token_id=lowerCamelCase,  bos_token_id=lowerCamelCase,  eos_token_id=lowerCamelCase,  is_encoder_decoder=lowerCamelCase,  decoder_start_token_id=lowerCamelCase,  forced_eos_token_id=lowerCamelCase,  **lowerCamelCase,  )





class 	__SCREAMING_SNAKE_CASE     (				lowerCAmelCase_       ):


					'''simple docstring'''





					@property
					def 		snake_case	(	self							:  Optional[int]					)-> Mapping[str, Mapping[int, str]]:
								if self.task in ["default", "seq2seq-lm"]:
											lowerCamelCase__		:		int		     =OrderedDict(
											    [
											        ('''input_ids''', {0: '''batch''', 1: '''encoder_sequence'''}),
											        ('''attention_mask''', {0: '''batch''', 1: '''encoder_sequence'''}),
											    ]					)

											if self.use_past:
														lowerCamelCase__		:		List[str]		     ={0: '''batch'''}
														lowerCamelCase__		:		Tuple		     ={0: '''batch''', 1: '''past_decoder_sequence + sequence'''}
											else:
														lowerCamelCase__		:		Union[str, Any]		     ={0: '''batch''', 1: '''decoder_sequence'''}
														lowerCamelCase__		:		Tuple		     ={0: '''batch''', 1: '''decoder_sequence'''}

											if self.use_past:
														self.fill_with_past_key_values_(lowerCamelCase,  direction='''inputs'''					)
								elif self.task == "causal-lm":
											# TODO: figure this case out.
											lowerCamelCase__		:		Optional[Any]		     =OrderedDict(
											    [
											        ('''input_ids''', {0: '''batch''', 1: '''encoder_sequence'''}),
											        ('''attention_mask''', {0: '''batch''', 1: '''encoder_sequence'''}),
											    ]					)
											if self.use_past:
														lowerCamelCase__     ,       lowerCamelCase__		:		List[str]		     =self.num_layers
														for i in range(lowerCamelCase					):
																	lowerCamelCase__		:		Optional[Any]		     ={0: '''batch''', 2: '''past_sequence + sequence'''}
																	lowerCamelCase__		:		Optional[int]		     ={0: '''batch''', 2: '''past_sequence + sequence'''}
								else:
											lowerCamelCase__		:		str		     =OrderedDict(
											    [
											        ('''input_ids''', {0: '''batch''', 1: '''encoder_sequence'''}),
											        ('''attention_mask''', {0: '''batch''', 1: '''encoder_sequence'''}),
											        ('''decoder_input_ids''', {0: '''batch''', 1: '''decoder_sequence'''}),
											        ('''decoder_attention_mask''', {0: '''batch''', 1: '''decoder_sequence'''}),
											    ]					)

								return common_inputs



					@property
					def 		snake_case	(	self							:  Dict					)-> Mapping[str, Mapping[int, str]]:
								if self.task in ["default", "seq2seq-lm"]:
											lowerCamelCase__		:		Dict		     =super().outputs
								else:
											lowerCamelCase__		:		Optional[Any]		     =super(lowerCamelCase,  self					).outputs
											if self.use_past:
														lowerCamelCase__     ,       lowerCamelCase__		:		str		     =self.num_layers
														for i in range(lowerCamelCase					):
																	lowerCamelCase__		:		Tuple		     ={0: '''batch''', 2: '''past_sequence + sequence'''}
																	lowerCamelCase__		:		Dict		     ={0: '''batch''', 2: '''past_sequence + sequence'''}
								return common_outputs



					def 		snake_case	(	self							:  List[str],  lowerCamelCase							:  PreTrainedTokenizer,  lowerCamelCase							:  int = -1,  lowerCamelCase							:  int = -1,  lowerCamelCase							:  bool = False,  lowerCamelCase							:  Optional[TensorType] = None,  )-> Mapping[str, Any]:
								lowerCamelCase__		:		Any		     =self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
								    lowerCamelCase,  lowerCamelCase,  lowerCamelCase,  lowerCamelCase,  lowerCamelCase					)

								# Generate decoder inputs
								lowerCamelCase__		:		str		     =seq_length if not self.use_past else 1
								lowerCamelCase__		:		Tuple		     =self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
								    lowerCamelCase,  lowerCamelCase,  lowerCamelCase,  lowerCamelCase,  lowerCamelCase					)
								lowerCamelCase__		:		str		     ={F'''decoder_{name}''': tensor for name, tensor in decoder_inputs.items()}
								lowerCamelCase__		:		Tuple		     =dict(**lowerCamelCase,  **lowerCamelCase					)

								if self.use_past:
											if not is_torch_available():
														raise ValueError('''Cannot generate dummy past_keys inputs without PyTorch installed.'''					)
											else:
														import torch
											lowerCamelCase__     ,       lowerCamelCase__		:		List[Any]		     =common_inputs['''input_ids'''].shape
											lowerCamelCase__		:		Optional[Any]		     =common_inputs['''decoder_input_ids'''].shape[1]
											lowerCamelCase__     ,       lowerCamelCase__		:		List[str]		     =self.num_attention_heads
											lowerCamelCase__		:		str		     =(
											    batch,
											    num_encoder_attention_heads,
											    encoder_seq_length,
											    self._config.hidden_size // num_encoder_attention_heads,
											)
											lowerCamelCase__		:		List[Any]		     =decoder_seq_length + 3
											lowerCamelCase__		:		Optional[int]		     =(
											    batch,
											    num_decoder_attention_heads,
											    decoder_past_length,
											    self._config.hidden_size // num_decoder_attention_heads,
											)

											lowerCamelCase__		:		Optional[Any]		     =torch.cat(
											    [common_inputs['''decoder_attention_mask'''], torch.ones(lowerCamelCase,  lowerCamelCase					)],  dim=1					)

											lowerCamelCase__		:		Tuple		     =[]
											# If the number of encoder and decoder layers are present in the model configuration, both are considered
											lowerCamelCase__     ,       lowerCamelCase__		:		int		     =self.num_layers
											lowerCamelCase__		:		Any		     =min(lowerCamelCase,  lowerCamelCase					)
											lowerCamelCase__		:		Any		     =max(lowerCamelCase,  lowerCamelCase					) - min_num_layers
											lowerCamelCase__		:		Dict		     ='''encoder''' if num_encoder_layers > num_decoder_layers else '''decoder'''

											for _ in range(lowerCamelCase					):
														common_inputs["past_key_values"].append(
														    (
														        torch.zeros(lowerCamelCase					),
														        torch.zeros(lowerCamelCase					),
														        torch.zeros(lowerCamelCase					),
														        torch.zeros(lowerCamelCase					),
														    )					)
											# TODO: test this.
											lowerCamelCase__		:		Union[str, Any]		     =encoder_shape if remaining_side_name == '''encoder''' else decoder_shape
											for _ in range(lowerCamelCase,  lowerCamelCase					):
														common_inputs["past_key_values"].append((torch.zeros(lowerCamelCase					), torch.zeros(lowerCamelCase					))					)
								return common_inputs



					def 		snake_case	(	self							:  List[str],  lowerCamelCase							:  PreTrainedTokenizer,  lowerCamelCase							:  int = -1,  lowerCamelCase							:  int = -1,  lowerCamelCase							:  bool = False,  lowerCamelCase							:  Optional[TensorType] = None,  )-> Mapping[str, Any]:
								lowerCamelCase__		:		int		     =self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
								    lowerCamelCase,  lowerCamelCase,  lowerCamelCase,  lowerCamelCase,  lowerCamelCase					)

								if self.use_past:
											if not is_torch_available():
														raise ValueError('''Cannot generate dummy past_keys inputs without PyTorch installed.'''					)
											else:
														import torch
											lowerCamelCase__     ,       lowerCamelCase__		:		List[str]		     =common_inputs['''input_ids'''].shape
											# Not using the same length for past_key_values
											lowerCamelCase__		:		Union[str, Any]		     =seqlen + 2
											lowerCamelCase__     ,       lowerCamelCase__		:		int		     =self.num_layers
											lowerCamelCase__     ,       lowerCamelCase__		:		Optional[int]		     =self.num_attention_heads
											lowerCamelCase__		:		int		     =(
											    batch,
											    num_encoder_attention_heads,
											    past_key_values_length,
											    self._config.hidden_size // num_encoder_attention_heads,
											)

											lowerCamelCase__		:		str		     =common_inputs['''attention_mask'''].dtype
											lowerCamelCase__		:		int		     =torch.cat(
											    [common_inputs['''attention_mask'''], torch.ones(lowerCamelCase,  lowerCamelCase,  dtype=lowerCamelCase					)],  dim=1					)
											lowerCamelCase__		:		str		     =[
											    (torch.zeros(lowerCamelCase					), torch.zeros(lowerCamelCase					)) for _ in range(lowerCamelCase					)
											]
								return common_inputs



					def 		snake_case	(	self							:  Optional[int],  lowerCamelCase							:  PreTrainedTokenizer,  lowerCamelCase							:  int = -1,  lowerCamelCase							:  int = -1,  lowerCamelCase							:  bool = False,  lowerCamelCase							:  Optional[TensorType] = None,  )-> Mapping[str, Any]:
								# Copied from OnnxConfig.generate_dummy_inputs
								# Did not use super(OnnxConfigWithPast, self).generate_dummy_inputs for code clarity.
								# If dynamic axis (-1) we forward with a fixed dimension of 2 samples to avoid optimizations made by ONNX
								lowerCamelCase__		:		int		     =compute_effective_axis_dimension(
								    lowerCamelCase,  fixed_dimension=OnnxConfig.default_fixed_batch,  num_token_to_add=0					)

								# If dynamic axis (-1) we forward with a fixed dimension of 8 tokens to avoid optimizations made by ONNX
								lowerCamelCase__		:		Optional[int]		     =tokenizer.num_special_tokens_to_add(lowerCamelCase					)
								lowerCamelCase__		:		Optional[int]		     =compute_effective_axis_dimension(
								    lowerCamelCase,  fixed_dimension=OnnxConfig.default_fixed_sequence,  num_token_to_add=lowerCamelCase					)

								# Generate dummy inputs according to compute batch and sequence
								lowerCamelCase__		:		Optional[int]		     =[''' '''.join([tokenizer.unk_token]					) * seq_length] * batch_size
								lowerCamelCase__		:		Optional[Any]		     =dict(tokenizer(lowerCamelCase,  return_tensors=lowerCamelCase					)					)
								return common_inputs



					def 		snake_case	(	self							:  List[Any],  lowerCamelCase							:  PreTrainedTokenizer,  lowerCamelCase							:  int = -1,  lowerCamelCase							:  int = -1,  lowerCamelCase							:  bool = False,  lowerCamelCase							:  Optional[TensorType] = None,  )-> Mapping[str, Any]:
								if self.task in ["default", "seq2seq-lm"]:
											lowerCamelCase__		:		Union[str, Any]		     =self._generate_dummy_inputs_for_default_and_seqaseq_lm(
											    lowerCamelCase,  batch_size=lowerCamelCase,  seq_length=lowerCamelCase,  is_pair=lowerCamelCase,  framework=lowerCamelCase					)

								elif self.task == "causal-lm":
											lowerCamelCase__		:		Union[str, Any]		     =self._generate_dummy_inputs_for_causal_lm(
											    lowerCamelCase,  batch_size=lowerCamelCase,  seq_length=lowerCamelCase,  is_pair=lowerCamelCase,  framework=lowerCamelCase					)
								else:
											lowerCamelCase__		:		List[Any]		     =self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
											    lowerCamelCase,  batch_size=lowerCamelCase,  seq_length=lowerCamelCase,  is_pair=lowerCamelCase,  framework=lowerCamelCase					)

								return common_inputs




					def 		snake_case	(	self							:  Optional[Any],  lowerCamelCase							:  Tuple,  lowerCamelCase							:  Union[str, Any],  lowerCamelCase							:  Dict,  lowerCamelCase							:  Any					)-> str:
								if self.task in ["default", "seq2seq-lm"]:
											lowerCamelCase__		:		Any		     =super()._flatten_past_key_values_(lowerCamelCase,  lowerCamelCase,  lowerCamelCase,  lowerCamelCase					)
								else:
											lowerCamelCase__		:		List[str]		     =super(lowerCamelCase,  self					)._flatten_past_key_values_(
											    lowerCamelCase,  lowerCamelCase,  lowerCamelCase,  lowerCamelCase					)




