






'''simple docstring'''







import inspect
import unittest
import warnings
from typing import List

from transformers import EfficientFormerConfig
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

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_FOR_IMAGE_CLASSIFICATION_MAPPING,
			    MODEL_MAPPING,
			    EfficientFormerForImageClassification,
			    EfficientFormerForImageClassificationWithTeacher,
			    EfficientFormerModel,
			)
			from transformers.models.efficientformer.modeling_efficientformer import (
			    EFFICIENTFORMER_PRETRAINED_MODEL_ARCHIVE_LIST,
			)


if is_vision_available():
			from PIL import Image

			from transformers import EfficientFormerImageProcessor

class _lowercase      :




							def __init__(				self:							Tuple     ,				UpperCamelCase__:							int     ,				UpperCamelCase__:							int = 13     ,				UpperCamelCase__:							int = 64     ,				UpperCamelCase__:							int = 2     ,				UpperCamelCase__:							int = 3     ,				UpperCamelCase__:							int = 3     ,				UpperCamelCase__:							bool = True     ,				UpperCamelCase__:							bool = True     ,				UpperCamelCase__:							int = 128     ,				UpperCamelCase__:							List[Any]=[16, 32, 64, 128]     ,				UpperCamelCase__:							int = 7     ,				UpperCamelCase__:							int = 4     ,				UpperCamelCase__:							int = 37     ,				UpperCamelCase__:							str = "gelu"     ,				UpperCamelCase__:							float = 0.1     ,				UpperCamelCase__:							float = 0.1     ,				UpperCamelCase__:							int = 10     ,				UpperCamelCase__:							float = 0.02     ,				UpperCamelCase__:							int = 2     ,				UpperCamelCase__:							int = 1     ,				UpperCamelCase__:							int = 128     ,				UpperCamelCase__:							List[int] = [2, 2, 2, 2]     ,				UpperCamelCase__:							int = 2     ,				UpperCamelCase__:							int = 2     ,				):
														lowerCamelCase__   :      List[Any]			    =			parent
														lowerCamelCase__   :      Tuple			    =			batch_size
														lowerCamelCase__   :      Tuple			    =			image_size
														lowerCamelCase__   :      Union[str, Any]			    =			patch_size
														lowerCamelCase__   :      int			    =			num_channels
														lowerCamelCase__   :      Dict			    =			is_training
														lowerCamelCase__   :      str			    =			use_labels
														lowerCamelCase__   :      List[str]			    =			hidden_size
														lowerCamelCase__   :      Tuple			    =			num_hidden_layers
														lowerCamelCase__   :      List[Any]			    =			num_attention_heads
														lowerCamelCase__   :      str			    =			intermediate_size
														lowerCamelCase__   :      Optional[Any]			    =			hidden_act
														lowerCamelCase__   :      Tuple			    =			hidden_dropout_prob
														lowerCamelCase__   :      Optional[int]			    =			attention_probs_dropout_prob
														lowerCamelCase__   :      str			    =			type_sequence_label_size
														lowerCamelCase__   :      List[Any]			    =			initializer_range
														lowerCamelCase__   :      Union[str, Any]			    =			encoder_stride
														lowerCamelCase__   :      Tuple			    =			num_attention_outputs
														lowerCamelCase__   :      Any			    =			embed_dim
														lowerCamelCase__   :      int			    =			embed_dim + 1
														lowerCamelCase__   :      Union[str, Any]			    =			resolution
														lowerCamelCase__   :      Tuple			    =			depths
														lowerCamelCase__   :      List[Any]			    =			hidden_sizes
														lowerCamelCase__   :      Tuple			    =			dim
														lowerCamelCase__   :      int			    =			mlp_expansion_ratio




							def 						lowerCamelCase_							(				self:							Union[str, Any]	):
														lowerCamelCase__   :      Union[str, Any]			    =			floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]	)

														lowerCamelCase__   :      Optional[Any]			    =			None
														if self.use_labels:
																					lowerCamelCase__   :      str			    =			ids_tensor([self.batch_size]     ,				self.type_sequence_label_size	)

														lowerCamelCase__   :      Optional[int]			    =			self.get_config()
														return config, pixel_values, labels




							def 						lowerCamelCase_							(				self:							Dict	):
														return EfficientFormerConfig(
														    image_size=self.image_size     ,				patch_size=self.patch_size     ,				num_channels=self.num_channels     ,				hidden_size=self.hidden_size     ,				num_hidden_layers=self.num_hidden_layers     ,				num_attention_heads=self.num_attention_heads     ,				intermediate_size=self.intermediate_size     ,				hidden_act=self.hidden_act     ,				hidden_dropout_prob=self.hidden_dropout_prob     ,				attention_probs_dropout_prob=self.attention_probs_dropout_prob     ,				is_decoder=UpperCamelCase__     ,				initializer_range=self.initializer_range     ,				encoder_stride=self.encoder_stride     ,				resolution=self.resolution     ,				depths=self.depths     ,				hidden_sizes=self.hidden_sizes     ,				dim=self.dim     ,				mlp_expansion_ratio=self.mlp_expansion_ratio     ,				)




							def 						lowerCamelCase_							(				self:							str     ,				UpperCamelCase__:							int     ,				UpperCamelCase__:							Optional[Any]     ,				UpperCamelCase__:							List[Any]	):
														lowerCamelCase__   :      List[Any]			    =			EfficientFormerModel(config=UpperCamelCase__	)
														model.to(UpperCamelCase__	)
														model.eval()
														lowerCamelCase__   :      int			    =			model(UpperCamelCase__	)
														self.parent.assertEqual(result.last_hidden_state.shape     ,				(self.batch_size, self.seq_length, self.hidden_size)	)




							def 						lowerCamelCase_							(				self:							List[Any]     ,				UpperCamelCase__:							Any     ,				UpperCamelCase__:							List[str]     ,				UpperCamelCase__:							Optional[Any]	):
														lowerCamelCase__   :      Dict			    =			self.type_sequence_label_size
														lowerCamelCase__   :      Dict			    =			EfficientFormerForImageClassification(UpperCamelCase__	)
														model.to(UpperCamelCase__	)
														model.eval()
														lowerCamelCase__   :      str			    =			model(UpperCamelCase__     ,				labels=UpperCamelCase__	)
														self.parent.assertEqual(result.logits.shape     ,				(self.batch_size, self.type_sequence_label_size)	)

														# test greyscale images
														lowerCamelCase__   :      Dict			    =			1
														lowerCamelCase__   :      Optional[int]			    =			EfficientFormerForImageClassification(UpperCamelCase__	)
														model.to(UpperCamelCase__	)
														model.eval()

														lowerCamelCase__   :      int			    =			floats_tensor([self.batch_size, 1, self.image_size, self.image_size]	)
														lowerCamelCase__   :      int			    =			model(UpperCamelCase__	)
														self.parent.assertEqual(result.logits.shape     ,				(self.batch_size, self.type_sequence_label_size)	)




							def 						lowerCamelCase_							(				self:							List[str]	):
														lowerCamelCase__   :      Optional[int]			    =			self.prepare_config_and_inputs()
														(
														    (
														    lowerCamelCase__
														)    ,						(
														    lowerCamelCase__
														)    ,						(
														    lowerCamelCase__
														)    ,						
														)   :      Optional[Any]			    =			config_and_inputs
														lowerCamelCase__   :      Optional[Any]			    =			{"""pixel_values""": pixel_values}
														return config, inputs_dict



@require_torch
class _lowercase      (							_lowercase							, _lowercase							, unittest.TestCase						):
							a							 =			(
							    (
							        EfficientFormerModel,
							        EfficientFormerForImageClassificationWithTeacher,
							        EfficientFormerForImageClassification,
							    )
							    if is_torch_available()
							    else ()
							)
							a							 =			(
							    {
							        """feature-extraction""": EfficientFormerModel,
							        """image-classification""": (
							            EfficientFormerForImageClassification,
							            EfficientFormerForImageClassificationWithTeacher,
							        ),
							    }
							    if is_torch_available()
							    else {}
							)
							a							 =			False

							a							 =			False
							a							 =			False
							a							 =			False




							def 						lowerCamelCase_							(				self:							int	):
														lowerCamelCase__   :      Optional[int]			    =			EfficientFormerModelTester(self	)
														lowerCamelCase__   :      List[Any]			    =			ConfigTester(
														    self     ,				config_class=UpperCamelCase__     ,				has_text_modality=UpperCamelCase__     ,				hidden_size=37	)




							def 						lowerCamelCase_							(				self:							List[str]	):
														self.config_tester.run_common_tests()




							@unittest.skip(reason="""EfficientFormer does not use inputs_embeds"""	)
							def 						lowerCamelCase_							(				self:							List[Any]	):
														pass




							@unittest.skip(reason="""EfficientFormer does not support input and output embeddings"""	)
							def 						lowerCamelCase_							(				self:							Union[str, Any]	):
														pass




							def 						lowerCamelCase_							(				self:							List[Any]	):
														lowerCamelCase__    ,						lowerCamelCase__   :      int			    =			self.model_tester.prepare_config_and_inputs_for_common()

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

																					lowerCamelCase__   :      Union[str, Any]			    =			["""pixel_values"""]
																					self.assertListEqual(arg_names[:1]     ,				UpperCamelCase__	)




							def 						lowerCamelCase_							(				self:							Tuple	):
														def check_hidden_states_output(UpperCamelCase__:							Optional[Any]     ,				UpperCamelCase__:							Union[str, Any]     ,				UpperCamelCase__:							Tuple	):
																					lowerCamelCase__   :      int			    =			model_class(UpperCamelCase__	)
																					model.to(UpperCamelCase__	)
																					model.eval()

																					with torch.no_grad():
																												lowerCamelCase__   :      Dict			    =			model(**self._prepare_for_class(UpperCamelCase__     ,				UpperCamelCase__	)	)

																					lowerCamelCase__   :      Tuple			    =			outputs.encoder_hidden_states if config.is_encoder_decoder else outputs.hidden_states

																					lowerCamelCase__   :      List[Any]			    =			getattr(
																					    self.model_tester     ,				"""expected_num_hidden_layers"""     ,				self.model_tester.num_hidden_layers + 1	)
																					self.assertEqual(len(UpperCamelCase__	)     ,				UpperCamelCase__	)

																					if hasattr(self.model_tester     ,				"""encoder_seq_length"""	):
																												lowerCamelCase__   :      List[str]			    =			self.model_tester.encoder_seq_length
																												if hasattr(self.model_tester     ,				"""chunk_length"""	) and self.model_tester.chunk_length > 1:
																																			lowerCamelCase__   :      Optional[Any]			    =			seq_length * self.model_tester.chunk_length
																					else:
																												lowerCamelCase__   :      Optional[int]			    =			self.model_tester.seq_length

																					self.assertListEqual(
																					    list(hidden_states[-1].shape[-2:]	)     ,				[seq_length, self.model_tester.hidden_size]     ,				)

																					if config.is_encoder_decoder:
																												lowerCamelCase__   :      str			    =			outputs.decoder_hidden_states

																												self.assertIsInstance(UpperCamelCase__     ,				(list, tuple)	)
																												self.assertEqual(len(UpperCamelCase__	)     ,				UpperCamelCase__	)
																												lowerCamelCase__   :      Dict			    =			getattr(self.model_tester     ,				"""seq_length"""     ,				UpperCamelCase__	)
																												lowerCamelCase__   :      Union[str, Any]			    =			getattr(self.model_tester     ,				"""decoder_seq_length"""     ,				UpperCamelCase__	)

																												self.assertListEqual(
																												    list(hidden_states[-1].shape[-2:]	)     ,				[decoder_seq_length, self.model_tester.hidden_size]     ,				)

														lowerCamelCase__    ,						lowerCamelCase__   :      Union[str, Any]			    =			self.model_tester.prepare_config_and_inputs_for_common()

														for model_class in self.all_model_classes:
																					lowerCamelCase__   :      Dict			    =			True
																					check_hidden_states_output(UpperCamelCase__     ,				UpperCamelCase__     ,				UpperCamelCase__	)

																					# check that output_hidden_states also work using config
																					del inputs_dict["output_hidden_states"]
																					lowerCamelCase__   :      Optional[Any]			    =			True

																					check_hidden_states_output(UpperCamelCase__     ,				UpperCamelCase__     ,				UpperCamelCase__	)




							def 						lowerCamelCase_							(				self:							str     ,				UpperCamelCase__:							str     ,				UpperCamelCase__:							List[str]     ,				UpperCamelCase__:							Any=False	):
														lowerCamelCase__   :      Optional[int]			    =			super()._prepare_for_class(UpperCamelCase__     ,				UpperCamelCase__     ,				return_labels=UpperCamelCase__	)

														if return_labels:
																					if model_class.__name__ == "EfficientFormerForImageClassificationWithTeacher":
																												del inputs_dict["labels"]

														return inputs_dict




							def 						lowerCamelCase_							(				self:							List[str]	):
														lowerCamelCase__   :      Optional[Any]			    =			self.model_tester.prepare_config_and_inputs()
														self.model_tester.create_and_check_model(*UpperCamelCase__	)




							@unittest.skip(reason="""EfficientFormer does not implement masked image modeling yet"""	)
							def 						lowerCamelCase_							(				self:							Dict	):
														lowerCamelCase__   :      Union[str, Any]			    =			self.model_tester.prepare_config_and_inputs()
														self.model_tester.create_and_check_for_masked_image_modeling(*UpperCamelCase__	)




							def 						lowerCamelCase_							(				self:							Tuple	):
														lowerCamelCase__   :      List[Any]			    =			self.model_tester.prepare_config_and_inputs()
														self.model_tester.create_and_check_for_image_classification(*UpperCamelCase__	)




							def 						lowerCamelCase_							(				self:							str	):
														if not self.model_tester.is_training:
																					return

														lowerCamelCase__    ,						lowerCamelCase__   :      Union[str, Any]			    =			self.model_tester.prepare_config_and_inputs_for_common()
														lowerCamelCase__   :      Union[str, Any]			    =			True

														for model_class in self.all_model_classes:
																					# EfficientFormerForImageClassificationWithTeacher supports inference-only
																					if (
																					    model_class in get_values(UpperCamelCase__	)
																					    or model_class.__name__ == "EfficientFormerForImageClassificationWithTeacher"
																					):
																												continue
																					lowerCamelCase__   :      List[str]			    =			model_class(UpperCamelCase__	)
																					model.to(UpperCamelCase__	)
																					model.train()
																					lowerCamelCase__   :      Any			    =			self._prepare_for_class(UpperCamelCase__     ,				UpperCamelCase__     ,				return_labels=UpperCamelCase__	)
																					lowerCamelCase__   :      Union[str, Any]			    =			model(**UpperCamelCase__	).loss
																					loss.backward()




							def 						lowerCamelCase_							(				self:							Any	):
														lowerCamelCase__    ,						lowerCamelCase__   :      List[str]			    =			self.model_tester.prepare_config_and_inputs_for_common()

														lowerCamelCase__   :      Optional[int]			    =			[
														    {"""title""": """multi_label_classification""", """num_labels""": 2, """dtype""": torch.float},
														    {"""title""": """single_label_classification""", """num_labels""": 1, """dtype""": torch.long},
														    {"""title""": """regression""", """num_labels""": 1, """dtype""": torch.float},
														]

														for model_class in self.all_model_classes:
																					if (
																					    model_class
																					    not in [
																					        *get_values(UpperCamelCase__	),
																					    ]
																					    or model_class.__name__ == "EfficientFormerForImageClassificationWithTeacher"
																					):
																												continue

																					for problem_type in problem_types:
																												with self.subTest(msg=F'''Testing {model_class} with {problem_type['title']}'''	):
																																			lowerCamelCase__   :      Optional[Any]			    =			problem_type["""title"""]
																																			lowerCamelCase__   :      Union[str, Any]			    =			problem_type["""num_labels"""]

																																			lowerCamelCase__   :      Any			    =			model_class(UpperCamelCase__	)
																																			model.to(UpperCamelCase__	)
																																			model.train()

																																			lowerCamelCase__   :      List[str]			    =			self._prepare_for_class(UpperCamelCase__     ,				UpperCamelCase__     ,				return_labels=UpperCamelCase__	)

																																			if problem_type["num_labels"] > 1:
																																										lowerCamelCase__   :      Union[str, Any]			    =			inputs["""labels"""].unsqueeze(1	).repeat(1     ,				problem_type["""num_labels"""]	)

																																			lowerCamelCase__   :      Tuple			    =			inputs["""labels"""].to(problem_type["""dtype"""]	)

																																			# This tests that we do not trigger the warning form PyTorch "Using a target size that is different
																																			# to the input size. This will likely lead to incorrect results due to broadcasting. Please ensure
																																			# they have the same size." which is a symptom something in wrong for the regression problem.
																																			# See https://github.com/huggingface/transformers/issues/11780
																																			with warnings.catch_warnings(record=UpperCamelCase__	) as warning_list:
																																										lowerCamelCase__   :      Dict			    =			model(**UpperCamelCase__	).loss
																																			for w in warning_list:
																																										if "Using a target size that is different to the input size" in str(w.message	):
																																																	raise ValueError(
																																																	    F'''Something is going wrong in the regression problem: intercepted {w.message}'''	)

																																			loss.backward()




							@slow
							def 						lowerCamelCase_							(				self:							List[Any]	):
														for model_name in EFFICIENTFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																					lowerCamelCase__   :      Dict			    =			EfficientFormerModel.from_pretrained(UpperCamelCase__	)
																					self.assertIsNotNone(UpperCamelCase__	)




							def 						lowerCamelCase_							(				self:							List[Any]	):
														lowerCamelCase__    ,						lowerCamelCase__   :      str			    =			self.model_tester.prepare_config_and_inputs_for_common()
														lowerCamelCase__   :      Optional[int]			    =			True

														lowerCamelCase__   :      Optional[Any]			    =			getattr(self.model_tester     ,				"""seq_length"""     ,				UpperCamelCase__	)
														lowerCamelCase__   :      Any			    =			getattr(self.model_tester     ,				"""encoder_seq_length"""     ,				UpperCamelCase__	)
														lowerCamelCase__   :      Optional[int]			    =			getattr(self.model_tester     ,				"""key_length"""     ,				UpperCamelCase__	)
														lowerCamelCase__   :      Any			    =			getattr(self.model_tester     ,				"""chunk_length"""     ,				UpperCamelCase__	)

														if chunk_length is not None and hasattr(self.model_tester     ,				"""num_hashes"""	):
																					lowerCamelCase__   :      str			    =			encoder_seq_length * self.model_tester.num_hashes

														for model_class in self.all_model_classes:
																					lowerCamelCase__   :      Optional[Any]			    =			True
																					lowerCamelCase__   :      int			    =			False
																					lowerCamelCase__   :      Any			    =			True
																					lowerCamelCase__   :      List[str]			    =			model_class(UpperCamelCase__	)
																					model.to(UpperCamelCase__	)
																					model.eval()
																					with torch.no_grad():
																												lowerCamelCase__   :      int			    =			model(**self._prepare_for_class(UpperCamelCase__     ,				UpperCamelCase__	)	)
																					lowerCamelCase__   :      str			    =			outputs.encoder_attentions if config.is_encoder_decoder else outputs.attentions
																					self.assertEqual(len(UpperCamelCase__	)     ,				self.model_tester.num_attention_outputs	)

																					# check that output_attentions also work using config
																					del inputs_dict["output_attentions"]
																					lowerCamelCase__   :      Optional[int]			    =			True
																					lowerCamelCase__   :      Union[str, Any]			    =			model_class(UpperCamelCase__	)
																					model.to(UpperCamelCase__	)
																					model.eval()
																					with torch.no_grad():
																												lowerCamelCase__   :      Tuple			    =			model(**self._prepare_for_class(UpperCamelCase__     ,				UpperCamelCase__	)	)
																					lowerCamelCase__   :      Any			    =			outputs.encoder_attentions if config.is_encoder_decoder else outputs.attentions
																					self.assertEqual(len(UpperCamelCase__	)     ,				self.model_tester.num_attention_outputs	)

																					if chunk_length is not None:
																												self.assertListEqual(
																												    list(attentions[0].shape[-4:]	)     ,				[self.model_tester.num_attention_heads, encoder_seq_length, chunk_length, encoder_key_length]     ,				)
																					else:
																												self.assertListEqual(
																												    list(attentions[0].shape[-3:]	)     ,				[self.model_tester.num_attention_heads, encoder_seq_length, encoder_key_length]     ,				)





def 					SCREAMING_SNAKE_CASE_			() ->			List[str]:
							lowerCamelCase__   :      List[Any]			    =			Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png""" )
							return image



@require_torch
@require_vision
class _lowercase      (							unittest.TestCase						):




							@cached_property
							def 						lowerCamelCase_							(				self:							Tuple	):
														return (
														    EfficientFormerImageProcessor.from_pretrained("""snap-research/efficientformer-l1-300"""	)
														    if is_vision_available()
														    else None
														)




							@slow
							def 						lowerCamelCase_							(				self:							Any	):
														lowerCamelCase__   :      Union[str, Any]			    =			EfficientFormerForImageClassification.from_pretrained("""snap-research/efficientformer-l1-300"""	).to(
														    UpperCamelCase__	)

														lowerCamelCase__   :      List[str]			    =			self.default_image_processor
														lowerCamelCase__   :      List[str]			    =			prepare_img()
														lowerCamelCase__   :      Optional[int]			    =			image_processor(images=UpperCamelCase__     ,				return_tensors="""pt"""	).to(UpperCamelCase__	)

														# forward pass
														with torch.no_grad():
																					lowerCamelCase__   :      Dict			    =			model(**UpperCamelCase__	)

														# verify the logits
														lowerCamelCase__   :      Dict			    =			(1, 1_000)
														self.assertEqual(outputs.logits.shape     ,				UpperCamelCase__	)

														lowerCamelCase__   :      Tuple			    =			torch.tensor([-0.0_555, 0.4_825, -0.0_852]	).to(UpperCamelCase__	)
														self.assertTrue(torch.allclose(outputs.logits[0][:3]     ,				UpperCamelCase__     ,				atol=1e-4	)	)




							@slow
							def 						lowerCamelCase_							(				self:							Any	):
														lowerCamelCase__   :      List[Any]			    =			EfficientFormerForImageClassificationWithTeacher.from_pretrained(
														    """snap-research/efficientformer-l1-300"""	).to(UpperCamelCase__	)

														lowerCamelCase__   :      Union[str, Any]			    =			self.default_image_processor
														lowerCamelCase__   :      List[str]			    =			prepare_img()
														lowerCamelCase__   :      Optional[int]			    =			image_processor(images=UpperCamelCase__     ,				return_tensors="""pt"""	).to(UpperCamelCase__	)

														# forward pass
														with torch.no_grad():
																					lowerCamelCase__   :      Dict			    =			model(**UpperCamelCase__	)

														# verify the logits
														lowerCamelCase__   :      Optional[int]			    =			(1, 1_000)
														self.assertEqual(outputs.logits.shape     ,				UpperCamelCase__	)

														lowerCamelCase__   :      Optional[int]			    =			torch.tensor([-0.1_312, 0.4_353, -1.0_499]	).to(UpperCamelCase__	)
														self.assertTrue(torch.allclose(outputs.logits[0][:3]     ,				UpperCamelCase__     ,				atol=1e-4	)	)









'''simple docstring'''







from __future__ import annotations





def 					SCREAMING_SNAKE_CASE_			(UpperCamelCase							,     UpperCamelCase ) ->			Dict:
							lowerCamelCase__   :      List[str]			    =			0
							lowerCamelCase__   :      Tuple			    =			len(UpperCamelCase ) - 1
							while left <= right:
														lowerCamelCase__   :      List[str]			    =			(left + right) // 2
														if left == right:
																					if sorted_list[middle] < item:
																												lowerCamelCase__   :      Any			    =			middle + 1
																					break
														elif sorted_list[middle] < item:
																					lowerCamelCase__   :      Optional[Any]			    =			middle + 1
														else:
																					lowerCamelCase__   :      Dict			    =			middle - 1
							sorted_list.insert(UpperCamelCase							,     UpperCamelCase )
							return sorted_list





def 					SCREAMING_SNAKE_CASE_			(UpperCamelCase							,     UpperCamelCase ) ->			Tuple:
							lowerCamelCase__   :      Any			    =			[]
							while left and right:
														if left[0][0] < right[0][0]:
																					result.append(left.pop(0 ) )
														else:
																					result.append(right.pop(0 ) )
							return result + left + right





def 					SCREAMING_SNAKE_CASE_			(UpperCamelCase ) ->			Any:
							lowerCamelCase__   :      Optional[Any]			    =			len(UpperCamelCase )
							if length <= 1:
														return list_ad
							lowerCamelCase__   :      Tuple			    =			length // 2
							return merge(sortlist_ad(list_ad[:middle] )							,     sortlist_ad(list_ad[middle:] ) )





def 					SCREAMING_SNAKE_CASE_			(UpperCamelCase ) ->			list[int]:

							if len(UpperCamelCase ) <= 1:
														return collection
							lowerCamelCase__   :      int			    =			[]
							lowerCamelCase__   :      int			    =			False
							for i in range(0							,     len(UpperCamelCase )							,     2 ):
														if i == len(UpperCamelCase ) - 1:
																					lowerCamelCase__   :      List[Any]			    =			True
														else:
																					if collection[i] < collection[i + 1]:
																												two_paired_list.append([collection[i], collection[i + 1]] )
																					else:
																												two_paired_list.append([collection[i + 1], collection[i]] )
							lowerCamelCase__   :      List[Any]			    =			sortlist_ad(UpperCamelCase )
							lowerCamelCase__   :      List[Any]			    =			[i[0] for i in sorted_list_ad]
							result.append(sorted_list_ad[-1][1] )
							if has_last_odd_item:
														lowerCamelCase__   :      int			    =			collection[-1]
														lowerCamelCase__   :      str			    =			binary_search_insertion(UpperCamelCase							,     UpperCamelCase )
							lowerCamelCase__   :      Any			    =			False
							for i in range(len(UpperCamelCase ) - 1 ):
														if result[i] == collection[-1] and has_last_odd_item:
																					lowerCamelCase__   :      Any			    =			True
														lowerCamelCase__   :      Dict			    =			sorted_list_ad[i][1]
														# If last_odd_item is inserted before the item's index,
														# you should forward index one more.
														if is_last_odd_item_inserted_before_this_index:
																					lowerCamelCase__   :      List[str]			    =			result[: i + 2] + binary_search_insertion(result[i + 2 :]							,     UpperCamelCase )
														else:
																					lowerCamelCase__   :      Dict			    =			result[: i + 1] + binary_search_insertion(result[i + 1 :]							,     UpperCamelCase )

							return result


if __name__ == "__main__":
			_A      :     Tuple       	=input('''Enter numbers separated by a comma:\n''').strip()
			_A      :     List[Any]       	=[int(item) for item in user_input.split(''',''')]
			print(merge_insertion_sort(unsorted))

