
from __future__ import annotations


def 							SCREAMING_SNAKE_CASE_      (			UpperCamelCase__		)     ->   list[int]:
      if len(UpperCamelCase__		) == 0:
            return array

      UpperCamelCase__    :   Optional[int]					=				min(UpperCamelCase__		), max(UpperCamelCase__		)

      # Compute the variables
      UpperCamelCase__    :   Optional[Any]					=				_max - _min + 1
      UpperCamelCase__    :   Any					=				[0] * holes_range, [0] * holes_range

      # Make the sorting.
      for i in array:
            UpperCamelCase__    :   Union[str, Any]					=				i - _min
            UpperCamelCase__    :   Optional[int]					=				i
            holes_repeat[index] += 1

      # Makes the array back by replacing the numbers.
      UpperCamelCase__    :   Optional[Any]					=				0
      for i in range(UpperCamelCase__		):
            while holes_repeat[i] > 0:
                  UpperCamelCase__    :   str					=				holes[i]
                  index += 1
                  holes_repeat[i] -= 1

    # Returns the sorted array.
      return array


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    lowerCamelCase      =input("Enter numbers separated by comma:\n")
    lowerCamelCase      =[int(x) for x in user_input.split(",")]
    print(pigeon_sort(unsorted))




from __future__ import annotations

import inspect
import unittest

import numpy as np

from transformers import DeiTConfig
from transformers.testing_utils import require_tf, require_vision, slow
from transformers.utils import cached_property, is_tf_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
    import tensorflow as tf

    from transformers import (
        TFDeiTForImageClassification,
        TFDeiTForImageClassificationWithTeacher,
        TFDeiTForMaskedImageModeling,
        TFDeiTModel,
    )
    from transformers.models.deit.modeling_tf_deit import TF_DEIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
    from PIL import Image

    from transformers import DeiTImageProcessor




class 				_lowerCamelCase :





     """simple docstring"""







     def __init__(							self						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE=1_3						,						__SCREAMING_SNAKE_CASE=3_0						,						__SCREAMING_SNAKE_CASE=2						,						__SCREAMING_SNAKE_CASE=3						,						__SCREAMING_SNAKE_CASE=True						,						__SCREAMING_SNAKE_CASE=True						,						__SCREAMING_SNAKE_CASE=3_2						,						__SCREAMING_SNAKE_CASE=2						,						__SCREAMING_SNAKE_CASE=4						,						__SCREAMING_SNAKE_CASE=3_7						,						__SCREAMING_SNAKE_CASE="gelu"						,						__SCREAMING_SNAKE_CASE=0.1						,						__SCREAMING_SNAKE_CASE=0.1						,						__SCREAMING_SNAKE_CASE=1_0						,						__SCREAMING_SNAKE_CASE=0.02						,						__SCREAMING_SNAKE_CASE=3						,						__SCREAMING_SNAKE_CASE=None						,						__SCREAMING_SNAKE_CASE=2						,						)  ->   Union[str, Any]:




           """simple docstring"""







           UpperCamelCase__    :   List[Any]					=				parent
           UpperCamelCase__    :   Optional[int]					=				batch_size
           UpperCamelCase__    :   Optional[Any]					=				image_size
           UpperCamelCase__    :   Optional[int]					=				patch_size
           UpperCamelCase__    :   Any					=				num_channels
           UpperCamelCase__    :   Optional[Any]					=				is_training
           UpperCamelCase__    :   Dict					=				use_labels
           UpperCamelCase__    :   Optional[int]					=				hidden_size
           UpperCamelCase__    :   str					=				num_hidden_layers
           UpperCamelCase__    :   int					=				num_attention_heads
           UpperCamelCase__    :   List[Any]					=				intermediate_size
           UpperCamelCase__    :   int					=				hidden_act
           UpperCamelCase__    :   int					=				hidden_dropout_prob
           UpperCamelCase__    :   Optional[Any]					=				attention_probs_dropout_prob
           UpperCamelCase__    :   Tuple					=				type_sequence_label_size
           UpperCamelCase__    :   Optional[int]					=				initializer_range
           UpperCamelCase__    :   List[str]					=				scope
           UpperCamelCase__    :   str					=				encoder_stride

           # in DeiT, the seq length equals the number of patches + 2 (we add 2 for the [CLS] and distilation tokens)
           UpperCamelCase__    :   Any					=				(image_size // patch_size) ** 2
           UpperCamelCase__    :   Any					=				num_patches + 2






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   Any:




           """simple docstring"""







           UpperCamelCase__    :   Tuple					=				floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]  )

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

           UpperCamelCase__    :   List[Any]					=				self.get_config()

           return config, pixel_values, labels






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   str:




           """simple docstring"""







           return DeiTConfig(
               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=__SCREAMING_SNAKE_CASE						,						initializer_range=self.initializer_range						,						encoder_stride=self.encoder_stride						,						)






     def    __SCREAMING_SNAKE_CASE			(							self						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE  )  ->   str:




           """simple docstring"""







           UpperCamelCase__    :   Tuple					=				TFDeiTModel(config=__SCREAMING_SNAKE_CASE  )
           UpperCamelCase__    :   Optional[int]					=				model(__SCREAMING_SNAKE_CASE  )
           self.parent.assertEqual(result.last_hidden_state.shape						,						(self.batch_size, self.seq_length, self.hidden_size)  )






     def    __SCREAMING_SNAKE_CASE			(							self						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE  )  ->   List[Any]:




           """simple docstring"""







           UpperCamelCase__    :   str					=				TFDeiTForMaskedImageModeling(config=__SCREAMING_SNAKE_CASE  )
           UpperCamelCase__    :   List[str]					=				model(__SCREAMING_SNAKE_CASE  )
           self.parent.assertEqual(
               result.reconstruction.shape						,						(self.batch_size, self.num_channels, self.image_size, self.image_size)  )

           # test greyscale images
           UpperCamelCase__    :   Optional[int]					=				1
           UpperCamelCase__    :   Any					=				TFDeiTForMaskedImageModeling(__SCREAMING_SNAKE_CASE  )

           UpperCamelCase__    :   Optional[Any]					=				floats_tensor([self.batch_size, 1, self.image_size, self.image_size]  )
           UpperCamelCase__    :   Any					=				model(__SCREAMING_SNAKE_CASE  )
           self.parent.assertEqual(result.reconstruction.shape						,						(self.batch_size, 1, self.image_size, self.image_size)  )






     def    __SCREAMING_SNAKE_CASE			(							self						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE  )  ->   Optional[int]:




           """simple docstring"""







           UpperCamelCase__    :   Optional[Any]					=				self.type_sequence_label_size
           UpperCamelCase__    :   Optional[Any]					=				TFDeiTForImageClassification(__SCREAMING_SNAKE_CASE  )
           UpperCamelCase__    :   Union[str, Any]					=				model(__SCREAMING_SNAKE_CASE						,						labels=__SCREAMING_SNAKE_CASE  )
           self.parent.assertEqual(result.logits.shape						,						(self.batch_size, self.type_sequence_label_size)  )

           # test greyscale images
           UpperCamelCase__    :   int					=				1
           UpperCamelCase__    :   int					=				TFDeiTForImageClassification(__SCREAMING_SNAKE_CASE  )

           UpperCamelCase__    :   Dict					=				floats_tensor([self.batch_size, 1, self.image_size, self.image_size]  )
           UpperCamelCase__    :   Optional[Any]					=				model(__SCREAMING_SNAKE_CASE						,						labels=__SCREAMING_SNAKE_CASE  )
           self.parent.assertEqual(result.logits.shape						,						(self.batch_size, self.type_sequence_label_size)  )






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   Tuple:




           """simple docstring"""







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




@require_tf
class 				_lowerCamelCase (      UpperCamelCase_	,							UpperCamelCase_	,							unittest.TestCase ):





     """simple docstring"""







     SCREAMING_SNAKE_CASE_		   =  (
         (
             TFDeiTModel,
             TFDeiTForImageClassification,
             TFDeiTForImageClassificationWithTeacher,
             TFDeiTForMaskedImageModeling,
         )
         if is_tf_available()
         else ()
     )
     SCREAMING_SNAKE_CASE_		   =  (
         {
             '''feature-extraction''': TFDeiTModel,
             '''image-classification''': (TFDeiTForImageClassification, TFDeiTForImageClassificationWithTeacher),
         }
         if is_tf_available()
         else {}
     )

     SCREAMING_SNAKE_CASE_		   =  False
     SCREAMING_SNAKE_CASE_		   =  False
     SCREAMING_SNAKE_CASE_		   =  False
     SCREAMING_SNAKE_CASE_		   =  False






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   List[Any]:




           """simple docstring"""







           UpperCamelCase__    :   List[Any]					=				TFDeiTModelTester(self  )
           UpperCamelCase__    :   str					=				ConfigTester(self						,						config_class=__SCREAMING_SNAKE_CASE						,						has_text_modality=__SCREAMING_SNAKE_CASE						,						hidden_size=3_7  )






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   Any:




           """simple docstring"""







           self.config_tester.run_common_tests()






     @unittest.skip(reason='''DeiT does not use inputs_embeds'''  )
     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   str:




           """simple docstring"""







           pass






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   Optional[Any]:




           """simple docstring"""







           UpperCamelCase__				,UpperCamelCase__    :   Optional[Any]					=				self.model_tester.prepare_config_and_inputs_for_common()

           for model_class in self.all_model_classes:
                 UpperCamelCase__    :   List[Any]					=				model_class(__SCREAMING_SNAKE_CASE  )
                 self.assertIsInstance(model.get_input_embeddings()						,						(tf.keras.layers.Layer)  )
                 UpperCamelCase__    :   Dict					=				model.get_output_embeddings()
                 self.assertTrue(x is None or isinstance(__SCREAMING_SNAKE_CASE						,						tf.keras.layers.Dense  )  )






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   Any:




           """simple docstring"""







           UpperCamelCase__				,UpperCamelCase__    :   List[str]					=				self.model_tester.prepare_config_and_inputs_for_common()

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

                 UpperCamelCase__    :   int					=				['''pixel_values''']
                 self.assertListEqual(arg_names[:1]						,						__SCREAMING_SNAKE_CASE  )






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   Tuple:




           """simple docstring"""







           UpperCamelCase__    :   str					=				self.model_tester.prepare_config_and_inputs()
           self.model_tester.create_and_check_model(*__SCREAMING_SNAKE_CASE  )






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   Any:




           """simple docstring"""







           UpperCamelCase__    :   Any					=				self.model_tester.prepare_config_and_inputs()
           self.model_tester.create_and_check_for_masked_image_modeling(*__SCREAMING_SNAKE_CASE  )






     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   Tuple:




           """simple docstring"""







           UpperCamelCase__    :   Any					=				self.model_tester.prepare_config_and_inputs()
           self.model_tester.create_and_check_for_image_classification(*__SCREAMING_SNAKE_CASE  )






     def    __SCREAMING_SNAKE_CASE			(							self						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE=False  )  ->   str:




           """simple docstring"""







           UpperCamelCase__    :   Optional[Any]					=				super()._prepare_for_class(__SCREAMING_SNAKE_CASE						,						__SCREAMING_SNAKE_CASE						,						return_labels=__SCREAMING_SNAKE_CASE  )

           if return_labels:
                 if "labels" in inputs_dict and "labels" not in inspect.signature(model_class.call  ).parameters:
                       del inputs_dict["labels"]

           return inputs_dict






     @slow
     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   Optional[int]:




           """simple docstring"""







           for model_name in TF_DEIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
                 UpperCamelCase__    :   Any					=				TFDeiTModel.from_pretrained(__SCREAMING_SNAKE_CASE  )
                 self.assertIsNotNone(__SCREAMING_SNAKE_CASE  )


def 							SCREAMING_SNAKE_CASE_      (			):
      UpperCamelCase__    :   Tuple					=				Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png'''		)
      return image




@require_tf
@require_vision
class 				_lowerCamelCase (      unittest.TestCase ):





     """simple docstring"""







     @cached_property
     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   List[Any]:




           """simple docstring"""







           return (
               DeiTImageProcessor.from_pretrained('''facebook/deit-base-distilled-patch16-224'''  )
               if is_vision_available()
               else None
           )






     @slow
     def    __SCREAMING_SNAKE_CASE			(							self  )  ->   Dict:




           """simple docstring"""







           UpperCamelCase__    :   Union[str, Any]					=				TFDeiTForImageClassificationWithTeacher.from_pretrained('''facebook/deit-base-distilled-patch16-224'''  )

           UpperCamelCase__    :   str					=				self.default_image_processor
           UpperCamelCase__    :   List[str]					=				prepare_img()
           UpperCamelCase__    :   int					=				image_processor(images=__SCREAMING_SNAKE_CASE						,						return_tensors='''tf'''  )

           # forward pass
           UpperCamelCase__    :   List[Any]					=				model(**__SCREAMING_SNAKE_CASE  )

           # verify the logits
           UpperCamelCase__    :   Union[str, Any]					=				tf.TensorShape((1, 1_0_0_0)  )
           self.assertEqual(outputs.logits.shape						,						__SCREAMING_SNAKE_CASE  )

           UpperCamelCase__    :   List[str]					=				tf.constant([-1.0266, 0.1912, -1.2861]  )

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


