


'''simple docstring'''






def      UpperCAmelCase      (		):







		'''simple docstring'''
		return [list(range(10_00 - i				,      -10_00 - i				,      -1 ) ) for i in range(10_00 )]


__A	:	Any     =     generate_large_matrix()
__A	:	Tuple     =     (
    [[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      UpperCAmelCase      (		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      UpperCAmelCase      (		lowerCamelCase_  :list[int] ):







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





def      UpperCAmelCase      (		lowerCamelCase_  :list[list[int]] ):







		'''simple docstring'''
		snake_case_		:							int			       =						0
		snake_case_		:							Union[str, Any]			       =						len(grid[0] )

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





def      UpperCAmelCase      (		lowerCamelCase_  :list[list[int]] ):







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





def      UpperCAmelCase      (		lowerCamelCase_  :list[list[int]] ):







		'''simple docstring'''
		snake_case_		:							Any			       =						0
		for row in grid:
				for i, number in enumerate(lowerCamelCase_ ):
						if number < 0:
								total += len(lowerCamelCase_ ) - i
								break
		return total





def      UpperCAmelCase      (		):







		'''simple docstring'''
		from timeit import timeit

		print("""Running benchmarks""" )
		snake_case_		:							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
		):
				snake_case_		:							Tuple			       =						timeit(F'''{func}(grid=grid)'''				,      setup=lowerCamelCase_				,      number=5_00 )
				print(F'''{func}() took {time:0.4f} seconds''' )


if __name__ == "__main__":
							import doctest

							doctest.testmod()
							benchmark()



'''simple docstring'''






import copy
import os
from typing import Union

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


__A	:	str     =     logging.get_logger(__name__)

__A	:	Dict     =     {
    'google/pix2struct-textcaps-base': (
        'https://huggingface.co/google/pix2struct-textcaps-base/resolve/main/config.json'
    ),
}
class 						__UpperCamelCase	(						lowercase__							):
							lowercase			:		Tuple   		=  'pix2struct_text_model'
							lowercase			:		int   		=  ['past_key_values']
							lowercase			:		int   		=  {
							    'hidden_size': 'hidden_size',
							    'num_attention_heads': 'num_heads',
							    'num_hidden_layers': 'num_layers',
							}





							def __init__(  self		:int  ,_UpperCamelCase		:List[str]=5_0_2_4_4  ,_UpperCamelCase		:Optional[Any]=7_6_8  ,_UpperCamelCase		:Dict=6_4  ,_UpperCamelCase		:Dict=2_0_4_8  ,_UpperCamelCase		:Optional[int]=1_2  ,_UpperCamelCase		:Union[str, Any]=1_2  ,_UpperCamelCase		:List[str]=3_2  ,_UpperCamelCase		:Union[str, Any]=1_2_8  ,_UpperCamelCase		:Tuple=0.1  ,_UpperCamelCase		:List[str]=1E-6  ,_UpperCamelCase		:List[Any]=1.0  ,_UpperCamelCase		:Optional[int]="gelu_new"  ,_UpperCamelCase		:Dict=0  ,_UpperCamelCase		:List[str]=False  ,_UpperCamelCase		:Optional[int]=0  ,_UpperCamelCase		:Dict=1  ,_UpperCamelCase		:List[Any]=False  ,_UpperCamelCase		:Tuple=True  ,**_UpperCamelCase		:List[Any]  ,):
									snake_case_		:							List[str]			       =						vocab_size
									snake_case_		:							Any			       =						hidden_size
									snake_case_		:							Any			       =						d_kv
									snake_case_		:							List[Any]			       =						d_ff
									snake_case_		:							Union[str, Any]			       =						num_layers
									snake_case_		:							Union[str, Any]			       =						num_heads
									snake_case_		:							str			       =						relative_attention_num_buckets
									snake_case_		:							Optional[int]			       =						relative_attention_max_distance
									snake_case_		:							Tuple			       =						dropout_rate
									snake_case_		:							Tuple			       =						layer_norm_epsilon
									snake_case_		:							Any			       =						initializer_factor
									snake_case_		:							List[Any]			       =						use_cache

									snake_case_		:							Optional[int]			       =						eos_token_id
									snake_case_		:							List[Any]			       =						decoder_start_token_id

									# for backwards compatibility
									snake_case_		:							List[str]			       =						dense_act_fn

									super().__init__(
									    pad_token_id=_UpperCamelCase  ,eos_token_id=_UpperCamelCase  ,decoder_start_token_id=_UpperCamelCase  ,tie_word_embeddings=_UpperCamelCase  ,is_decoder=_UpperCamelCase  ,**_UpperCamelCase  ,)





							@classmethod
							def 		a__   (  cls		:Optional[int]  ,_UpperCamelCase		:Union[str, os.PathLike]  ,**_UpperCamelCase		:Optional[int]			):
									cls._set_token_in_kwargs(_UpperCamelCase			)

									snake_case_       ,      snake_case_		:							Optional[Any]			       =						cls.get_config_dict(_UpperCamelCase  ,**_UpperCamelCase			)

									# get the text config dict if we are loading from Pix2StructConfig
									if config_dict.get("""model_type"""			) == "pix2struct":
											snake_case_		:							Optional[int]			       =						config_dict["""text_config"""]

									if "model_type" in config_dict and hasattr(cls  ,"""model_type"""			) and config_dict["model_type"] != cls.model_type:
											logger.warning(
											    F'''You are using a model of type {config_dict["model_type"]} to instantiate a model of type '''
											    F'''{cls.model_type}. This is not supported for all configurations of models and can yield errors.'''			)

									return cls.from_dict(_UpperCamelCase  ,**_UpperCamelCase			)





class 						__UpperCamelCase	(						lowercase__							):
							lowercase			:		Dict   		=  'pix2struct_vision_model'





							def __init__(  self		:List[str]  ,_UpperCamelCase		:Any=7_6_8  ,_UpperCamelCase		:List[str]=7_6_8  ,_UpperCamelCase		:List[Any]=2_0_4_8  ,_UpperCamelCase		:Union[str, Any]=6_4  ,_UpperCamelCase		:int=1_2  ,_UpperCamelCase		:int=1_2  ,_UpperCamelCase		:Any="gelu_new"  ,_UpperCamelCase		:Optional[int]=1E-6  ,_UpperCamelCase		:List[Any]=0.0  ,_UpperCamelCase		:Union[str, Any]=0.0  ,_UpperCamelCase		:int=1E-1_0  ,_UpperCamelCase		:str=1.0  ,_UpperCamelCase		:Optional[int]=4_0_9_6  ,_UpperCamelCase		:str=3_2  ,_UpperCamelCase		:Union[str, Any]=1_2_8  ,**_UpperCamelCase		:Union[str, Any]  ,):
									super().__init__(**_UpperCamelCase			)

									snake_case_		:							str			       =						hidden_size
									snake_case_		:							Tuple			       =						patch_embed_hidden_size
									snake_case_		:							Optional[int]			       =						d_ff
									snake_case_		:							Dict			       =						dropout_rate
									snake_case_		:							Optional[int]			       =						num_hidden_layers
									snake_case_		:							Dict			       =						num_attention_heads
									snake_case_		:							Union[str, Any]			       =						initializer_range
									snake_case_		:							Optional[Any]			       =						initializer_factor
									snake_case_		:							List[str]			       =						attention_dropout
									snake_case_		:							List[str]			       =						layer_norm_eps
									snake_case_		:							List[str]			       =						dense_act_fn
									snake_case_		:							int			       =						seq_len
									snake_case_		:							str			       =						relative_attention_num_buckets
									snake_case_		:							Tuple			       =						relative_attention_max_distance
									snake_case_		:							List[str]			       =						d_kv





							@classmethod
							def 		a__   (  cls		:Optional[Any]  ,_UpperCamelCase		:Union[str, os.PathLike]  ,**_UpperCamelCase		:List[str]			):
									cls._set_token_in_kwargs(_UpperCamelCase			)

									snake_case_       ,      snake_case_		:							Tuple			       =						cls.get_config_dict(_UpperCamelCase  ,**_UpperCamelCase			)

									# get the vision config dict if we are loading from Pix2StructConfig
									if config_dict.get("""model_type"""			) == "pix2struct":
											snake_case_		:							Dict			       =						config_dict["""vision_config"""]

									if "model_type" in config_dict and hasattr(cls  ,"""model_type"""			) and config_dict["model_type"] != cls.model_type:
											logger.warning(
											    F'''You are using a model of type {config_dict["model_type"]} to instantiate a model of type '''
											    F'''{cls.model_type}. This is not supported for all configurations of models and can yield errors.'''			)

									return cls.from_dict(_UpperCamelCase  ,**_UpperCamelCase			)





class 						__UpperCamelCase	(						lowercase__							):
							lowercase			:		Union[str, Any]   		=  'pix2struct'
							lowercase			:		int   		=  True





							def __init__(  self		:int  ,_UpperCamelCase		:Tuple=None  ,_UpperCamelCase		:Optional[int]=None  ,_UpperCamelCase		:Dict=1.0  ,_UpperCamelCase		:Optional[int]=0.02  ,_UpperCamelCase		:Tuple=False  ,_UpperCamelCase		:List[str]=False  ,_UpperCamelCase		:Dict=True  ,**_UpperCamelCase		:Union[str, Any]  ,):
									super().__init__(tie_word_embeddings=_UpperCamelCase  ,is_encoder_decoder=_UpperCamelCase  ,**_UpperCamelCase			)

									if text_config is None:
											snake_case_		:							Optional[int]			       =						{}
											logger.info("""text_config is None. Initializing the Pix2StructTextConfig with default values."""			)

									if vision_config is None:
											snake_case_		:							List[str]			       =						{}
											logger.info("""vision_config is None. Initializing the Pix2StructVisionConfig with default values."""			)

									snake_case_		:							Optional[int]			       =						PixaStructTextConfig(**_UpperCamelCase			)
									snake_case_		:							List[str]			       =						PixaStructVisionConfig(**_UpperCamelCase			)

									snake_case_		:							Any			       =						self.text_config.decoder_start_token_id
									snake_case_		:							List[Any]			       =						self.text_config.pad_token_id
									snake_case_		:							Optional[int]			       =						self.text_config.eos_token_id

									snake_case_		:							Optional[int]			       =						initializer_factor
									snake_case_		:							List[str]			       =						initializer_range

									snake_case_		:							Union[str, Any]			       =						self.initializer_range
									snake_case_		:							str			       =						self.initializer_range

									snake_case_		:							Dict			       =						is_vqa





							@classmethod
							def 		a__   (  cls		:Any  ,_UpperCamelCase		:PixaStructTextConfig  ,_UpperCamelCase		:PixaStructVisionConfig  ,**_UpperCamelCase		:Any			):
									return cls(text_config=text_config.to_dict()  ,vision_config=vision_config.to_dict()  ,**_UpperCamelCase			)





							def 		a__   (  self		:Optional[int]			):
									snake_case_		:							int			       =						copy.deepcopy(self.__dict__			)
									snake_case_		:							str			       =						self.text_config.to_dict()
									snake_case_		:							Tuple			       =						self.vision_config.to_dict()
									snake_case_		:							Any			       =						self.__class__.model_type
									return output