
"""simple docstring"""







import inspect
import unittest

from transformers import SegformerConfig, is_torch_available, is_vision_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
							import torch

							from transformers import (
							    MODEL_MAPPING,
							    SegformerForImageClassification,
							    SegformerForSemanticSegmentation,
							    SegformerModel,
							)
							from transformers.models.segformer.modeling_segformer import SEGFORMER_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
							from PIL import Image

							from transformers import SegformerImageProcessor




class  A__       (	__a):

		def 							__lowerCamelCase							(      self ):
			__lowerCAmelCase			:						Dict									=      self.config_class(**self.inputs_dict )
			self.parent.assertTrue(hasattr(_SCREAMING_SNAKE_CASE       ,		'hidden_sizes' ) )
			self.parent.assertTrue(hasattr(_SCREAMING_SNAKE_CASE       ,		'num_attention_heads' ) )
			self.parent.assertTrue(hasattr(_SCREAMING_SNAKE_CASE       ,		'num_encoder_blocks' ) )




class  A__       :

		def __init__(      self       ,		_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE=13       ,		_SCREAMING_SNAKE_CASE=64       ,		_SCREAMING_SNAKE_CASE=3       ,		_SCREAMING_SNAKE_CASE=4       ,		_SCREAMING_SNAKE_CASE=[2, 2, 2, 2]       ,		_SCREAMING_SNAKE_CASE=[8, 4, 2, 1]       ,		_SCREAMING_SNAKE_CASE=[16, 32, 64, 1_28]       ,		_SCREAMING_SNAKE_CASE=[1, 4, 8, 16]       ,		_SCREAMING_SNAKE_CASE=[1, 2, 4, 8]       ,		_SCREAMING_SNAKE_CASE=True       ,		_SCREAMING_SNAKE_CASE=True       ,		_SCREAMING_SNAKE_CASE="gelu"       ,		_SCREAMING_SNAKE_CASE=0.1       ,		_SCREAMING_SNAKE_CASE=0.1       ,		_SCREAMING_SNAKE_CASE=0.02       ,		_SCREAMING_SNAKE_CASE=3       ,		_SCREAMING_SNAKE_CASE=None       ,		):
			__lowerCAmelCase			:						Optional[int]									=      parent
			__lowerCAmelCase			:						int									=      batch_size
			__lowerCAmelCase			:						List[str]									=      image_size
			__lowerCAmelCase			:						Optional[Any]									=      num_channels
			__lowerCAmelCase			:						Dict									=      num_encoder_blocks
			__lowerCAmelCase			:						List[Any]									=      sr_ratios
			__lowerCAmelCase			:						str									=      depths
			__lowerCAmelCase			:						Any									=      hidden_sizes
			__lowerCAmelCase			:						List[str]									=      downsampling_rates
			__lowerCAmelCase			:						List[Any]									=      num_attention_heads
			__lowerCAmelCase			:						str									=      is_training
			__lowerCAmelCase			:						int									=      use_labels
			__lowerCAmelCase			:						int									=      hidden_act
			__lowerCAmelCase			:						Dict									=      hidden_dropout_prob
			__lowerCAmelCase			:						List[str]									=      attention_probs_dropout_prob
			__lowerCAmelCase			:						Tuple									=      initializer_range
			__lowerCAmelCase			:						Dict									=      num_labels
			__lowerCAmelCase			:						Dict									=      scope

		def 							__lowerCamelCase							(      self ):
			__lowerCAmelCase			:						Any									=      floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size] )

			__lowerCAmelCase			:						str									=      None
			if self.use_labels:
				__lowerCAmelCase			:						Union[str, Any]									=      ids_tensor([self.batch_size, self.image_size, self.image_size]       ,		self.num_labels )

			__lowerCAmelCase			:						Union[str, Any]									=      self.get_config()
			return config, pixel_values, labels

		def 							__lowerCamelCase							(      self ):
			return SegformerConfig(
			    image_size=self.image_size       ,		num_channels=self.num_channels       ,		num_encoder_blocks=self.num_encoder_blocks       ,		depths=self.depths       ,		hidden_sizes=self.hidden_sizes       ,		num_attention_heads=self.num_attention_heads       ,		hidden_act=self.hidden_act       ,		hidden_dropout_prob=self.hidden_dropout_prob       ,		attention_probs_dropout_prob=self.attention_probs_dropout_prob       ,		initializer_range=self.initializer_range       ,		)

		def 							__lowerCamelCase							(      self       ,		_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE ):
			__lowerCAmelCase			:						Tuple									=      SegformerModel(config=_SCREAMING_SNAKE_CASE )
			model.to(_SCREAMING_SNAKE_CASE )
			model.eval()
			__lowerCAmelCase			:						Dict									=      model(_SCREAMING_SNAKE_CASE )
			__lowerCAmelCase			:						Dict									=      self.image_size // (self.downsampling_rates[-1] * 2)
			self.parent.assertEqual(
			    result.last_hidden_state.shape       ,		(self.batch_size, self.hidden_sizes[-1], expected_height, expected_width) )

		def 							__lowerCamelCase							(      self       ,		_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE ):
			__lowerCAmelCase			:						List[Any]									=      self.num_labels
			__lowerCAmelCase			:						Dict									=      SegformerForSemanticSegmentation(_SCREAMING_SNAKE_CASE )
			model.to(_SCREAMING_SNAKE_CASE )
			model.eval()
			__lowerCAmelCase			:						int									=      model(_SCREAMING_SNAKE_CASE )
			self.parent.assertEqual(
			    result.logits.shape       ,		(self.batch_size, self.num_labels, self.image_size // 4, self.image_size // 4) )
			__lowerCAmelCase			:						int									=      model(_SCREAMING_SNAKE_CASE       ,		labels=_SCREAMING_SNAKE_CASE )
			self.parent.assertEqual(
			    result.logits.shape       ,		(self.batch_size, self.num_labels, self.image_size // 4, self.image_size // 4) )
			self.parent.assertGreater(result.loss       ,		0.0 )

		def 							__lowerCamelCase							(      self       ,		_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE ):
			__lowerCAmelCase			:						Optional[int]									=      1
			__lowerCAmelCase			:						Any									=      SegformerForSemanticSegmentation(config=_SCREAMING_SNAKE_CASE )
			model.to(_SCREAMING_SNAKE_CASE )
			model.eval()
			__lowerCAmelCase			:						int									=      torch.randint(0       ,		1       ,		(self.batch_size, self.image_size, self.image_size) ).to(_SCREAMING_SNAKE_CASE )
			__lowerCAmelCase			:						Optional[Any]									=      model(_SCREAMING_SNAKE_CASE       ,		labels=_SCREAMING_SNAKE_CASE )
			self.parent.assertGreater(result.loss       ,		0.0 )







		def 							__lowerCamelCase							(      self ):
			__lowerCAmelCase			:						Union[str, Any]									=      self.prepare_config_and_inputs()
			__lowerCAmelCase			,   __lowerCAmelCase			,   __lowerCAmelCase			:						int									=      config_and_inputs
			__lowerCAmelCase			:						Optional[int]									=      {'pixel_values': pixel_values}
			return config, inputs_dict




@require_torch
class  A__       (	__a       ,     __a       ,     unittest.TestCase):
		A_						:       Optional[Any]				   =	(
		    (
		        SegformerModel,
		        SegformerForSemanticSegmentation,
		        SegformerForImageClassification,
		    )
		    if is_torch_available()
		    else ()
		)
		A_						:       Dict				   =	(
		    {
		        """feature-extraction""": SegformerModel,
		        """image-classification""": SegformerForImageClassification,
		        """image-segmentation""": SegformerForSemanticSegmentation,
		    }
		    if is_torch_available()
		    else {}
		)

		A_						:       Union[str, Any]				   =	True
		A_						:       str				   =	False
		A_						:       Dict				   =	False
		A_						:       int				   =	False

		def 							__lowerCamelCase							(      self ):
			__lowerCAmelCase			:						Tuple									=      SegformerModelTester(self )
			__lowerCAmelCase			:						Tuple									=      SegformerConfigTester(self       ,		config_class=_SCREAMING_SNAKE_CASE )

		def 							__lowerCamelCase							(      self ):
			self.config_tester.run_common_tests()

		def 							__lowerCamelCase							(      self ):
			__lowerCAmelCase			:						Optional[Any]									=      self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_model(*_SCREAMING_SNAKE_CASE )

		def 							__lowerCamelCase							(      self ):
			__lowerCAmelCase			:						Optional[int]									=      self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_for_binary_image_segmentation(*_SCREAMING_SNAKE_CASE )

		def 							__lowerCamelCase							(      self ):
			__lowerCAmelCase			:						List[Any]									=      self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_for_image_segmentation(*_SCREAMING_SNAKE_CASE )

		@unittest.skip('SegFormer does not use inputs_embeds' )
		def 							__lowerCamelCase							(      self ):
			pass

		@unittest.skip('SegFormer does not have get_input_embeddings method and get_output_embeddings methods' )
		def 							__lowerCamelCase							(      self ):
			pass

		def 							__lowerCamelCase							(      self ):
			__lowerCAmelCase			,   __lowerCAmelCase			:						List[str]									=      self.model_tester.prepare_config_and_inputs_for_common()

			for model_class in self.all_model_classes:
				__lowerCAmelCase			:						Any									=      model_class(_SCREAMING_SNAKE_CASE )
				__lowerCAmelCase			:						Any									=      inspect.signature(model.forward )
				# signature.parameters is an OrderedDict => so arg_names order is deterministic
				__lowerCAmelCase			:						Optional[Any]									=      [*signature.parameters.keys()]

				__lowerCAmelCase			:						Dict									=      ['pixel_values']
				self.assertListEqual(arg_names[:1]       ,		_SCREAMING_SNAKE_CASE )

		def 							__lowerCamelCase							(      self ):
			__lowerCAmelCase			,   __lowerCAmelCase			:						int									=      self.model_tester.prepare_config_and_inputs_for_common()
			__lowerCAmelCase			:						str									=      True

			for model_class in self.all_model_classes:
				__lowerCAmelCase			:						Tuple									=      True
				__lowerCAmelCase			:						List[Any]									=      False
				__lowerCAmelCase			:						List[Any]									=      True
				__lowerCAmelCase			:						Union[str, Any]									=      model_class(_SCREAMING_SNAKE_CASE )
				model.to(_SCREAMING_SNAKE_CASE )
				model.eval()
				with torch.no_grad():
					__lowerCAmelCase			:						Dict									=      model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE ) )
				__lowerCAmelCase			:						Union[str, Any]									=      outputs.attentions

				__lowerCAmelCase			:						Optional[int]									=      sum(self.model_tester.depths )
				self.assertEqual(len(_SCREAMING_SNAKE_CASE )       ,		_SCREAMING_SNAKE_CASE )

				# check that output_attentions also work using config
				del inputs_dict["output_attentions"]
				__lowerCAmelCase			:						List[str]									=      True
				__lowerCAmelCase			:						Any									=      model_class(_SCREAMING_SNAKE_CASE )
				model.to(_SCREAMING_SNAKE_CASE )
				model.eval()
				with torch.no_grad():
					__lowerCAmelCase			:						str									=      model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE ) )
				__lowerCAmelCase			:						List[Any]									=      outputs.attentions

				self.assertEqual(len(_SCREAMING_SNAKE_CASE )       ,		_SCREAMING_SNAKE_CASE )

				# verify the first attentions (first block, first layer)
				__lowerCAmelCase			:						Optional[Any]									=      (self.model_tester.image_size // 4) ** 2
				__lowerCAmelCase			:						int									=      (self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
				self.assertListEqual(
				    list(attentions[0].shape[-3:] )       ,		[self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len]       ,		)

				# verify the last attentions (last block, last layer)
				__lowerCAmelCase			:						Any									=      (self.model_tester.image_size // 32) ** 2
				__lowerCAmelCase			:						Dict									=      (self.model_tester.image_size // (32 * self.model_tester.sr_ratios[-1])) ** 2
				self.assertListEqual(
				    list(attentions[-1].shape[-3:] )       ,		[self.model_tester.num_attention_heads[-1], expected_seq_len, expected_reduced_seq_len]       ,		)
				__lowerCAmelCase			:						Any									=      len(_SCREAMING_SNAKE_CASE )

				# Check attention is always last and order is fine
				__lowerCAmelCase			:						int									=      True
				__lowerCAmelCase			:						Optional[Any]									=      True
				__lowerCAmelCase			:						List[Any]									=      model_class(_SCREAMING_SNAKE_CASE )
				model.to(_SCREAMING_SNAKE_CASE )
				model.eval()
				with torch.no_grad():
					__lowerCAmelCase			:						List[str]									=      model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE ) )

				self.assertEqual(out_len + 1       ,		len(_SCREAMING_SNAKE_CASE ) )

				__lowerCAmelCase			:						List[str]									=      outputs.attentions

				self.assertEqual(len(_SCREAMING_SNAKE_CASE )       ,		_SCREAMING_SNAKE_CASE )
				# verify the first attentions (first block, first layer)
				__lowerCAmelCase			:						Optional[int]									=      (self.model_tester.image_size // 4) ** 2
				__lowerCAmelCase			:						Optional[int]									=      (self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
				self.assertListEqual(
				    list(self_attentions[0].shape[-3:] )       ,		[self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len]       ,		)

		def 							__lowerCamelCase							(      self ):

			def check_hidden_states_output(_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE ):
				__lowerCAmelCase			:						int									=      model_class(_SCREAMING_SNAKE_CASE )
				model.to(_SCREAMING_SNAKE_CASE )
				model.eval()

				with torch.no_grad():
					__lowerCAmelCase			:						Dict									=      model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE ) )

				__lowerCAmelCase			:						int									=      outputs.hidden_states

				__lowerCAmelCase			:						List[str]									=      self.model_tester.num_encoder_blocks
				self.assertEqual(len(_SCREAMING_SNAKE_CASE )       ,		_SCREAMING_SNAKE_CASE )

				# verify the first hidden states (first block)
				self.assertListEqual(
				    list(hidden_states[0].shape[-3:] )       ,		[
				        self.model_tester.hidden_sizes[0],
				        self.model_tester.image_size // 4,
				        self.model_tester.image_size // 4,
				    ]       ,		)

			__lowerCAmelCase			,   __lowerCAmelCase			:						str									=      self.model_tester.prepare_config_and_inputs_for_common()

			for model_class in self.all_model_classes:
				__lowerCAmelCase			:						str									=      True
				check_hidden_states_output(_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE )

				# check that output_hidden_states also work using config
				del inputs_dict["output_hidden_states"]
				__lowerCAmelCase			:						int									=      True

				check_hidden_states_output(_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE )

		def 							__lowerCamelCase							(      self ):

			if not self.model_tester.is_training:
				return

			__lowerCAmelCase			,   __lowerCAmelCase			:						Tuple									=      self.model_tester.prepare_config_and_inputs_for_common()
			__lowerCAmelCase			:						Optional[int]									=      True

			for model_class in self.all_model_classes:
				if model_class in get_values(_SCREAMING_SNAKE_CASE ):
					continue

				__lowerCAmelCase			:						Optional[int]									=      model_class(_SCREAMING_SNAKE_CASE )
				model.to(_SCREAMING_SNAKE_CASE )
				model.train()
				__lowerCAmelCase			:						Optional[int]									=      self._prepare_for_class(_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE       ,		return_labels=_SCREAMING_SNAKE_CASE )
				__lowerCAmelCase			:						Tuple									=      model(**_SCREAMING_SNAKE_CASE ).loss
				loss.backward()

		@unittest.skip('Will be fixed soon by reducing the size of the model used for common tests.' )
		def 							__lowerCamelCase							(      self ):
			pass







		@slow
		def 							__lowerCamelCase							(      self ):

			for model_name in SEGFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
				__lowerCAmelCase			:						Union[str, Any]									=      SegformerModel.from_pretrained(_SCREAMING_SNAKE_CASE )
				self.assertIsNotNone(_SCREAMING_SNAKE_CASE )



def     __lowerCAmelCase				():
	__lowerCAmelCase			:						List[str]									=      Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png'		)
	return image




@require_torch
class  A__       (	unittest.TestCase):

		@slow
		def 							__lowerCamelCase							(      self ):
			__lowerCAmelCase			:						Optional[Any]									=      SegformerImageProcessor(
			    image_scale=(5_12, 5_12)       ,		keep_ratio=_SCREAMING_SNAKE_CASE       ,		align=_SCREAMING_SNAKE_CASE       ,		do_random_crop=_SCREAMING_SNAKE_CASE )
			__lowerCAmelCase			:						Optional[Any]									=      SegformerForSemanticSegmentation.from_pretrained('nvidia/segformer-b0-finetuned-ade-512-512' ).to(
			    _SCREAMING_SNAKE_CASE )

			__lowerCAmelCase			:						Dict									=      prepare_img()
			__lowerCAmelCase			:						Optional[Any]									=      image_processor(images=_SCREAMING_SNAKE_CASE       ,		return_tensors='pt' )
			__lowerCAmelCase			:						Optional[int]									=      encoded_inputs.pixel_values.to(_SCREAMING_SNAKE_CASE )

			with torch.no_grad():
				__lowerCAmelCase			:						Tuple									=      model(_SCREAMING_SNAKE_CASE )

			__lowerCAmelCase			:						Tuple									=      torch.Size((1, model.config.num_labels, 1_28, 1_28) )
			self.assertEqual(outputs.logits.shape       ,		_SCREAMING_SNAKE_CASE )

			__lowerCAmelCase			:						List[Any]									=      torch.tensor(
			    [
			        [[-4.6310, -5.5232, -6.2356], [-5.1921, -6.1444, -6.5996], [-5.4424, -6.2790, -6.7574]],
			        [[-12.1391, -13.3122, -13.9554], [-12.8732, -13.9352, -14.3563], [-12.9438, -13.8226, -14.2513]],
			        [[-12.5134, -13.4686, -14.4915], [-12.8669, -14.4343, -14.7758], [-13.2523, -14.5819, -15.0694]],
			    ] ).to(_SCREAMING_SNAKE_CASE )
			self.assertTrue(torch.allclose(outputs.logits[0, :3, :3, :3]       ,		_SCREAMING_SNAKE_CASE       ,		atol=1E-4 ) )

		@slow
		def 							__lowerCamelCase							(      self ):
			__lowerCAmelCase			:						Any									=      SegformerImageProcessor(
			    image_scale=(5_12, 5_12)       ,		keep_ratio=_SCREAMING_SNAKE_CASE       ,		align=_SCREAMING_SNAKE_CASE       ,		do_random_crop=_SCREAMING_SNAKE_CASE )
			__lowerCAmelCase			:						Tuple									=      SegformerForSemanticSegmentation.from_pretrained(
			    'nvidia/segformer-b1-finetuned-cityscapes-1024-1024' ).to(_SCREAMING_SNAKE_CASE )

			__lowerCAmelCase			:						Any									=      prepare_img()
			__lowerCAmelCase			:						Optional[int]									=      image_processor(images=_SCREAMING_SNAKE_CASE       ,		return_tensors='pt' )
			__lowerCAmelCase			:						Optional[int]									=      encoded_inputs.pixel_values.to(_SCREAMING_SNAKE_CASE )

			with torch.no_grad():
				__lowerCAmelCase			:						Optional[Any]									=      model(_SCREAMING_SNAKE_CASE )

			__lowerCAmelCase			:						str									=      torch.Size((1, model.config.num_labels, 1_28, 1_28) )
			self.assertEqual(outputs.logits.shape       ,		_SCREAMING_SNAKE_CASE )

			__lowerCAmelCase			:						Optional[Any]									=      torch.tensor(
			    [
			        [[-13.5748, -13.9111, -12.6500], [-14.3500, -15.3683, -14.2328], [-14.7532, -16.0424, -15.6087]],
			        [[-17.1651, -15.8725, -12.9653], [-17.2580, -17.3718, -14.8223], [-16.6058, -16.8783, -16.7452]],
			        [[-3.6456, -3.0209, -1.4203], [-3.0797, -3.1959, -2.0000], [-1.8757, -1.9217, -1.6997]],
			    ] ).to(_SCREAMING_SNAKE_CASE )
			self.assertTrue(torch.allclose(outputs.logits[0, :3, :3, :3]       ,		_SCREAMING_SNAKE_CASE       ,		atol=1E-1 ) )







		@slow
		def 							__lowerCamelCase							(      self ):
			__lowerCAmelCase			:						List[Any]									=      SegformerImageProcessor(
			    image_scale=(5_12, 5_12)       ,		keep_ratio=_SCREAMING_SNAKE_CASE       ,		align=_SCREAMING_SNAKE_CASE       ,		do_random_crop=_SCREAMING_SNAKE_CASE )
			__lowerCAmelCase			:						Optional[int]									=      SegformerForSemanticSegmentation.from_pretrained('nvidia/segformer-b0-finetuned-ade-512-512' ).to(
			    _SCREAMING_SNAKE_CASE )

			__lowerCAmelCase			:						str									=      prepare_img()
			__lowerCAmelCase			:						List[str]									=      image_processor(images=_SCREAMING_SNAKE_CASE       ,		return_tensors='pt' )
			__lowerCAmelCase			:						Dict									=      encoded_inputs.pixel_values.to(_SCREAMING_SNAKE_CASE )

			with torch.no_grad():
				__lowerCAmelCase			:						Optional[Any]									=      model(_SCREAMING_SNAKE_CASE )

			__lowerCAmelCase			:						Dict									=      outputs.logits.detach().cpu()

			__lowerCAmelCase			:						List[str]									=      image_processor.post_process_semantic_segmentation(outputs=_SCREAMING_SNAKE_CASE       ,		target_sizes=[(5_00, 3_00)] )
			__lowerCAmelCase			:						Tuple									=      torch.Size((5_00, 3_00) )
			self.assertEqual(segmentation[0].shape       ,		_SCREAMING_SNAKE_CASE )

			__lowerCAmelCase			:						Union[str, Any]									=      image_processor.post_process_semantic_segmentation(outputs=_SCREAMING_SNAKE_CASE )
			__lowerCAmelCase			:						List[Any]									=      torch.Size((1_28, 1_28) )
			self.assertEqual(segmentation[0].shape       ,		_SCREAMING_SNAKE_CASE )





'''simple docstring'''







from __future__ import annotations





def 						snake_case_							(_a	:							Dict    ,   _a	:							str    ,   _a	:							Optional[Any]    ,   _a	:							List[str]     ):  # noqa: E741
    while r - l > 1:
        UpperCAmelCase			       =		(l + r) // 2
        if v[m] >= key:
            UpperCAmelCase			       =		m
        else:
            UpperCAmelCase			       =		m  # noqa: E741
    return r





def 						snake_case_							(_a	:							list[int]     ):
    if len(_a     ) == 0:
        return 0

    UpperCAmelCase			       =		[0] * len(_a     )
    UpperCAmelCase			       =		1

    UpperCAmelCase			       =		v[0]

    for i in range(1    ,   len(_a     )     ):
        if v[i] < tail[0]:
            UpperCAmelCase			       =		v[i]
        elif v[i] > tail[length - 1]:
            UpperCAmelCase			       =		v[i]
            length += 1
        else:
            UpperCAmelCase			       =		v[i]

    return length


if __name__ == "__main__":
   import doctest

   doctest.testmod()




