



"""simple docstring"""





import inspect
import unittest

from transformers import ViTConfig
from transformers.testing_utils import (
    require_accelerate,
    require_torch,
    require_torch_gpu,
    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 torch import nn

  from transformers import ViTForImageClassification, ViTForMaskedImageModeling, ViTModel
  from transformers.models.vit.modeling_vit import VIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
  from PIL import Image

  from transformers import ViTImageProcessor
class    lowercase__     :







       '''simple docstring'''


       def __init__(							self    :						int	,       _UpperCAmelCase    :						Dict	,       _UpperCAmelCase    :						Dict=13	,       _UpperCAmelCase    :						Optional[int]=30	,       _UpperCAmelCase    :						Optional[Any]=2	,       _UpperCAmelCase    :						Optional[Any]=3	,       _UpperCAmelCase    :						Dict=True	,       _UpperCAmelCase    :						Optional[Any]=True	,       _UpperCAmelCase    :						Tuple=32	,       _UpperCAmelCase    :						List[Any]=5	,       _UpperCAmelCase    :						str=4	,       _UpperCAmelCase    :						List[str]=37	,       _UpperCAmelCase    :						List[str]="gelu"	,       _UpperCAmelCase    :						List[str]=0.1	,       _UpperCAmelCase    :						Optional[int]=0.1	,       _UpperCAmelCase    :						Union[str, Any]=10	,       _UpperCAmelCase    :						str=0.02	,       _UpperCAmelCase    :						Any=None	,       _UpperCAmelCase    :						Dict=2	,       )				->		Any:


             '''simple docstring'''




             UpperCAmelCase_    				=							parent
             UpperCAmelCase_    				=							batch_size
             UpperCAmelCase_    				=							image_size
             UpperCAmelCase_    				=							patch_size
             UpperCAmelCase_    				=							num_channels
             UpperCAmelCase_    				=							is_training
             UpperCAmelCase_    				=							use_labels
             UpperCAmelCase_    				=							hidden_size
             UpperCAmelCase_    				=							num_hidden_layers
             UpperCAmelCase_    				=							num_attention_heads
             UpperCAmelCase_    				=							intermediate_size
             UpperCAmelCase_    				=							hidden_act
             UpperCAmelCase_    				=							hidden_dropout_prob
             UpperCAmelCase_    				=							attention_probs_dropout_prob
             UpperCAmelCase_    				=							type_sequence_label_size
             UpperCAmelCase_    				=							initializer_range
             UpperCAmelCase_    				=							scope
             UpperCAmelCase_    				=							encoder_stride

             # in ViT, the seq length equals the number of patches + 1 (we add 1 for the [CLS] token)
             UpperCAmelCase_    				=							(image_size // patch_size) ** 2
             UpperCAmelCase_    				=							num_patches + 1



       def   lowercase__       (							self    :						List[str]					)				->		int:


             '''simple docstring'''




             UpperCAmelCase_    				=							floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]					)

             UpperCAmelCase_    				=							None
             if self.use_labels:
                   UpperCAmelCase_    				=							ids_tensor([self.batch_size]	,       self.type_sequence_label_size					)

             UpperCAmelCase_    				=							self.get_config()

             return config, pixel_values, labels



       def   lowercase__       (							self    :						Tuple					)				->		Dict:


             '''simple docstring'''




             return ViTConfig(
                 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	,       )



       def   lowercase__       (							self    :						Any	,       _UpperCAmelCase    :						Dict	,       _UpperCAmelCase    :						List[Any]	,       _UpperCAmelCase    :						List[str]					)				->		Dict:


             '''simple docstring'''




             UpperCAmelCase_    				=							ViTModel(config=_UpperCAmelCase					)
             model.to(_UpperCAmelCase					)
             model.eval()
             UpperCAmelCase_    				=							model(_UpperCAmelCase					)
             self.parent.assertEqual(result.last_hidden_state.shape	,       (self.batch_size, self.seq_length, self.hidden_size)					)



       def   lowercase__       (							self    :						Any	,       _UpperCAmelCase    :						int	,       _UpperCAmelCase    :						Optional[int]	,       _UpperCAmelCase    :						int					)				->		str:


             '''simple docstring'''




             UpperCAmelCase_    				=							ViTForMaskedImageModeling(config=_UpperCAmelCase					)
             model.to(_UpperCAmelCase					)
             model.eval()
             UpperCAmelCase_    				=							model(_UpperCAmelCase					)
             self.parent.assertEqual(
                 result.reconstruction.shape	,       (self.batch_size, self.num_channels, self.image_size, self.image_size)					)

             # test greyscale images
             UpperCAmelCase_    				=							1
             UpperCAmelCase_    				=							ViTForMaskedImageModeling(_UpperCAmelCase					)
             model.to(_UpperCAmelCase					)
             model.eval()

             UpperCAmelCase_    				=							floats_tensor([self.batch_size, 1, self.image_size, self.image_size]					)
             UpperCAmelCase_    				=							model(_UpperCAmelCase					)
             self.parent.assertEqual(result.reconstruction.shape	,       (self.batch_size, 1, self.image_size, self.image_size)					)



       def   lowercase__       (							self    :						Union[str, Any]	,       _UpperCAmelCase    :						List[Any]	,       _UpperCAmelCase    :						str	,       _UpperCAmelCase    :						List[str]					)				->		Optional[int]:


             '''simple docstring'''




             UpperCAmelCase_    				=							self.type_sequence_label_size
             UpperCAmelCase_    				=							ViTForImageClassification(_UpperCAmelCase					)
             model.to(_UpperCAmelCase					)
             model.eval()
             UpperCAmelCase_    				=							model(_UpperCAmelCase	,       labels=_UpperCAmelCase					)
             self.parent.assertEqual(result.logits.shape	,       (self.batch_size, self.type_sequence_label_size)					)

             # test greyscale images
             UpperCAmelCase_    				=							1
             UpperCAmelCase_    				=							ViTForImageClassification(_UpperCAmelCase					)
             model.to(_UpperCAmelCase					)
             model.eval()

             UpperCAmelCase_    				=							floats_tensor([self.batch_size, 1, self.image_size, self.image_size]					)
             UpperCAmelCase_    				=							model(_UpperCAmelCase					)
             self.parent.assertEqual(result.logits.shape	,       (self.batch_size, self.type_sequence_label_size)					)







       def   lowercase__       (							self    :						List[str]					)				->		Optional[Any]:


             '''simple docstring'''




             UpperCAmelCase_    				=							self.prepare_config_and_inputs()
             (
                 (
                 UpperCAmelCase_
             )				,					(
                 UpperCAmelCase_
             )				,					(
                 UpperCAmelCase_
             )				,					
             )    				=							config_and_inputs
             UpperCAmelCase_    				=							{"pixel_values": pixel_values}
             return config, inputs_dict



@require_torch
class    lowercase__     (					SCREAMING_SNAKE_CASE       ,      SCREAMING_SNAKE_CASE       ,      unittest.TestCase   ):







       '''simple docstring'''


       UpperCamelCase		=  (
           (
               ViTModel,
               ViTForImageClassification,
               ViTForMaskedImageModeling,
           )
           if is_torch_available()
           else ()
       )
       UpperCamelCase		=  (
           {'''feature-extraction''': ViTModel, '''image-classification''': ViTForImageClassification}
           if is_torch_available()
           else {}
       )
       UpperCamelCase		=  True

       UpperCamelCase		=  False
       UpperCamelCase		=  False
       UpperCamelCase		=  False



       def   lowercase__       (							self    :						List[Any]					)				->		Optional[Any]:


             '''simple docstring'''




             UpperCAmelCase_    				=							ViTModelTester(self					)
             UpperCAmelCase_    				=							ConfigTester(self	,       config_class=_UpperCAmelCase	,       has_text_modality=_UpperCAmelCase	,       hidden_size=37					)



       def   lowercase__       (							self    :						Tuple					)				->		List[str]:


             '''simple docstring'''




             self.config_tester.run_common_tests()



       @unittest.skip(reason="ViT does not use inputs_embeds"					)
       def   lowercase__       (							self    :						Optional[Any]					)				->		int:


             '''simple docstring'''




             pass



       def   lowercase__       (							self    :						Optional[int]					)				->		Optional[Any]:


             '''simple docstring'''




             UpperCAmelCase_				,					UpperCAmelCase_    				=							self.model_tester.prepare_config_and_inputs_for_common()

             for model_class in self.all_model_classes:
                   UpperCAmelCase_    				=							model_class(_UpperCAmelCase					)
                   self.assertIsInstance(model.get_input_embeddings()	,       (nn.Module)					)
                   UpperCAmelCase_    				=							model.get_output_embeddings()
                   self.assertTrue(x is None or isinstance(_UpperCAmelCase	,       nn.Linear					)					)



       def   lowercase__       (							self    :						str					)				->		str:


             '''simple docstring'''




             UpperCAmelCase_				,					UpperCAmelCase_    				=							self.model_tester.prepare_config_and_inputs_for_common()

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

                   UpperCAmelCase_    				=							["pixel_values"]
                   self.assertListEqual(arg_names[:1]	,       _UpperCAmelCase					)



       def   lowercase__       (							self    :						Optional[int]					)				->		List[Any]:


             '''simple docstring'''




             UpperCAmelCase_    				=							self.model_tester.prepare_config_and_inputs()
             self.model_tester.create_and_check_model(*_UpperCAmelCase					)



       def   lowercase__       (							self    :						Optional[Any]					)				->		List[Any]:


             '''simple docstring'''




             UpperCAmelCase_    				=							self.model_tester.prepare_config_and_inputs()
             self.model_tester.create_and_check_for_masked_image_modeling(*_UpperCAmelCase					)



       def   lowercase__       (							self    :						int					)				->		List[Any]:


             '''simple docstring'''




             UpperCAmelCase_    				=							self.model_tester.prepare_config_and_inputs()
             self.model_tester.create_and_check_for_image_classification(*_UpperCAmelCase					)







       @slow
       def   lowercase__       (							self    :						Union[str, Any]					)				->		Optional[int]:


             '''simple docstring'''




             for model_name in VIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
                   UpperCAmelCase_    				=							ViTModel.from_pretrained(_UpperCAmelCase					)
                   self.assertIsNotNone(_UpperCAmelCase					)



def      a__			(   ):
      UpperCAmelCase_    				=							Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"   )
      return image


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







       '''simple docstring'''


       @cached_property
       def   lowercase__       (							self    :						Optional[Any]					)				->		Optional[int]:


             '''simple docstring'''




             return ViTImageProcessor.from_pretrained("google/vit-base-patch16-224"					) if is_vision_available() else None



       @slow
       def   lowercase__       (							self    :						Tuple					)				->		Union[str, Any]:


             '''simple docstring'''




             UpperCAmelCase_    				=							ViTForImageClassification.from_pretrained("google/vit-base-patch16-224"					).to(_UpperCAmelCase					)

             UpperCAmelCase_    				=							self.default_image_processor
             UpperCAmelCase_    				=							prepare_img()
             UpperCAmelCase_    				=							image_processor(images=_UpperCAmelCase	,       return_tensors="pt"					).to(_UpperCAmelCase					)

             # forward pass
             with torch.no_grad():
                   UpperCAmelCase_    				=							model(**_UpperCAmelCase					)

             # verify the logits
             UpperCAmelCase_    				=							torch.Size((1, 1000)					)
             self.assertEqual(outputs.logits.shape	,       _UpperCAmelCase					)

             UpperCAmelCase_    				=							torch.tensor([-0.2744, 0.8215, -0.0836]					).to(_UpperCAmelCase					)

             self.assertTrue(torch.allclose(outputs.logits[0, :3]	,       _UpperCAmelCase	,       atol=1e-4					)					)



       @slow
       def   lowercase__       (							self    :						Tuple					)				->		Union[str, Any]:


             '''simple docstring'''




             UpperCAmelCase_    				=							ViTModel.from_pretrained("facebook/dino-vits8"					).to(_UpperCAmelCase					)

             UpperCAmelCase_    				=							ViTImageProcessor.from_pretrained("facebook/dino-vits8"	,       size=480					)
             UpperCAmelCase_    				=							prepare_img()
             UpperCAmelCase_    				=							image_processor(images=_UpperCAmelCase	,       return_tensors="pt"					)
             UpperCAmelCase_    				=							inputs.pixel_values.to(_UpperCAmelCase					)

             # forward pass
             with torch.no_grad():
                   UpperCAmelCase_    				=							model(_UpperCAmelCase	,       interpolate_pos_encoding=_UpperCAmelCase					)

             # verify the logits
             UpperCAmelCase_    				=							torch.Size((1, 3601, 384)					)
             self.assertEqual(outputs.last_hidden_state.shape	,       _UpperCAmelCase					)

             UpperCAmelCase_    				=							torch.tensor(
                 [[4.2340, 4.3906, -6.6692], [4.5463, 1.8928, -6.7257], [4.4429, 0.8496, -5.8585]]					).to(_UpperCAmelCase					)

             self.assertTrue(torch.allclose(outputs.last_hidden_state[0, :3, :3]	,       _UpperCAmelCase	,       atol=1e-4					)					)







       @slow
       @require_accelerate
       @require_torch_gpu
       def   lowercase__       (							self    :						Optional[Any]					)				->		int:


             '''simple docstring'''




             UpperCAmelCase_    				=							ViTModel.from_pretrained("facebook/dino-vits8"	,       torch_dtype=torch.floataa	,       device_map="auto"					)
             UpperCAmelCase_    				=							self.default_image_processor

             UpperCAmelCase_    				=							prepare_img()
             UpperCAmelCase_    				=							image_processor(images=_UpperCAmelCase	,       return_tensors="pt"					)
             UpperCAmelCase_    				=							inputs.pixel_values.to(_UpperCAmelCase					)

             # forward pass to make sure inference works in fp16
             with torch.no_grad():
                   UpperCAmelCase_    				=							model(_UpperCAmelCase					)









"""simple docstring"""





from __future__ import annotations
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   ):
      UpperCAmelCase_    				=							[]
      UpperCAmelCase_				,					UpperCAmelCase_    				=							input_list[low:mid], input_list[mid : high + 1]
      while left and right:
            result.append((left if left[0] <= right[0] else right).pop(0   )   )
      UpperCAmelCase_    				=							result + left + right
      return input_list
def      a__			(   lowerCAmelCase__   ):
      if len(lowerCAmelCase__   ) <= 1:
            return input_list
      UpperCAmelCase_    				=							list(lowerCAmelCase__   )

      # iteration for two-way merging
      UpperCAmelCase_    				=							2
      while p <= len(lowerCAmelCase__   ):
            # getting low, high and middle value for merge-sort of single list
            for i in range(0			,    len(lowerCAmelCase__   )			,    lowerCAmelCase__   ):
                  UpperCAmelCase_    				=							i
                  UpperCAmelCase_    				=							i + p - 1
                  UpperCAmelCase_    				=							(low + high + 1) // 2
                  UpperCAmelCase_    				=							merge(lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   )
            # final merge of last two parts
            if p * 2 >= len(lowerCAmelCase__   ):
                  UpperCAmelCase_    				=							i
                  UpperCAmelCase_    				=							merge(lowerCAmelCase__			,    0			,    lowerCAmelCase__			,    len(lowerCAmelCase__   ) - 1   )
                  break
            p *= 2

      return input_list


if __name__ == "__main__":
  lowerCamelCase      =		input("""Enter numbers separated by a comma:\n""").strip()
  if user_input == "":
    lowerCamelCase      =		[]
  else:
    lowerCamelCase      =		[int(item.strip()) for item in user_input.split(""",""")]
  print(iter_merge_sort(unsorted))




