"""simple docstring"""






def     UpperCAmelCase__ (       )				->					list[list[int]]:
      '''simple docstring'''


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


__lowerCAmelCase					: int        =generate_large_matrix()
__lowerCAmelCase					: 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     UpperCAmelCase__ (       lowerCAmelCase__  :Tuple	)				->					None:
      '''simple docstring'''


      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     UpperCAmelCase__ (       lowerCAmelCase__  :str	)				->					int:
      '''simple docstring'''


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


def     UpperCAmelCase__ (       lowerCAmelCase__  :Dict	)				->					int:
      '''simple docstring'''


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

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


def     UpperCAmelCase__ (       lowerCAmelCase__  :List[Any]	)				->					int:
      '''simple docstring'''


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


def     UpperCAmelCase__ (       lowerCAmelCase__  :Union[str, Any]	)				->					int:
      '''simple docstring'''


      lowercase														=			0
      for row in grid:
            for i, number in enumerate(lowercase_	):
                  if number < 0:
                        total += len(lowercase_	) - i
                        break
      return total


def     UpperCAmelCase__ (       )				->					None:
      '''simple docstring'''


      from timeit import timeit

      print("""Running benchmarks"""	)
      lowercase														=			(
          "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
      ):
            lowercase														=			timeit(f'{func}(grid=grid)'      ,	setup=lowercase_      ,	number=5_0_0	)
            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


__lowerCAmelCase					: Any        =logging.get_logger(__name__)

__lowerCAmelCase					: Union[str, Any]        ={
    """facebook/timesformer""": """https://huggingface.co/facebook/timesformer/resolve/main/config.json""",
}





class 				_A		( lowerCAmelCase			):
      snake_case__    :     Optional[Any]													=			'timesformer'

      def __init__(		self	, __lowerCAmelCase=224	, __lowerCAmelCase=16	, __lowerCAmelCase=3	, __lowerCAmelCase=8	, __lowerCAmelCase=768	, __lowerCAmelCase=12	, __lowerCAmelCase=12	, __lowerCAmelCase=3072	, __lowerCAmelCase="gelu"	, __lowerCAmelCase=0.0	, __lowerCAmelCase=0.0	, __lowerCAmelCase=0.0_2	, __lowerCAmelCase=1E-6	, __lowerCAmelCase=True	, __lowerCAmelCase="divided_space_time"	, __lowerCAmelCase=0	, **__lowerCAmelCase	, ):







            """simple docstring"""



            super().__init__(**__lowerCAmelCase		)

            lowercase														=			image_size
            lowercase														=			patch_size
            lowercase														=			num_channels
            lowercase														=			num_frames

            lowercase														=			hidden_size
            lowercase														=			num_hidden_layers
            lowercase														=			num_attention_heads
            lowercase														=			intermediate_size
            lowercase														=			hidden_act
            lowercase														=			hidden_dropout_prob
            lowercase														=			attention_probs_dropout_prob
            lowercase														=			initializer_range
            lowercase														=			layer_norm_eps
            lowercase														=			qkv_bias

            lowercase														=			attention_type
            lowercase														=			drop_path_rate



