




from __future__ import annotations







def 			lowerCamelCase_		(       UpperCamelCase__				:      list[int]      )     ->       list[int]:





				"""simple docstring"""


				if len(UpperCamelCase__      ) == 0:
								return array

				__lowerCamelCase       ,						__lowerCamelCase		       =    min(UpperCamelCase__      ), max(UpperCamelCase__      )

				# Compute the variables
				__lowerCamelCase		       =    _max - _min + 1
				__lowerCamelCase       ,						__lowerCamelCase		       =    [0] * holes_range, [0] * holes_range

				# Make the sorting.
				for i in array:
								__lowerCamelCase		       =    i - _min
								__lowerCamelCase		       =    i
								holes_repeat[index] += 1

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

    # Returns the sorted array.
				return array


if __name__ == "__main__":
					import doctest

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








import collections
import inspect
import unittest

from transformers import FocalNetConfig
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_backbone_common import BackboneTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, _config_zero_init, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
					import torch
					from torch import nn

					from transformers import (
					    FocalNetBackbone,
					    FocalNetForImageClassification,
					    FocalNetForMaskedImageModeling,
					    FocalNetModel,
					)
					from transformers.models.focalnet.modeling_focalnet import FOCALNET_PRETRAINED_MODEL_ARCHIVE_LIST

if is_vision_available():
					from PIL import Image

					from transformers import AutoImageProcessor







class     __lowerCAmelCase :

			"""simple docstring"""







			def __init__(      self			,						lowerCamelCase__			,						lowerCamelCase__=13			,						lowerCamelCase__=32			,						lowerCamelCase__=2			,						lowerCamelCase__=3			,						lowerCamelCase__=16			,						lowerCamelCase__=[32, 64, 128]			,						lowerCamelCase__=[1, 2, 1]			,						lowerCamelCase__=[2, 2, 4]			,						lowerCamelCase__=2			,						lowerCamelCase__=2.0			,						lowerCamelCase__=True			,						lowerCamelCase__=0.0			,						lowerCamelCase__=0.0			,						lowerCamelCase__=0.1			,						lowerCamelCase__="gelu"			,						lowerCamelCase__=False			,						lowerCamelCase__=True			,						lowerCamelCase__=0.02			,						lowerCamelCase__=1e-5			,						lowerCamelCase__=True			,						lowerCamelCase__=None			,						lowerCamelCase__=True			,						lowerCamelCase__=10			,						lowerCamelCase__=8			,						lowerCamelCase__=["stage1", "stage2"]			,						lowerCamelCase__=[1, 2]			,						)    ->      int:



							'''simple docstring'''
							__lowerCamelCase		       =    parent
							__lowerCamelCase		       =    batch_size
							__lowerCamelCase		       =    image_size
							__lowerCamelCase		       =    patch_size
							__lowerCamelCase		       =    num_channels
							__lowerCamelCase		       =    embed_dim
							__lowerCamelCase		       =    hidden_sizes
							__lowerCamelCase		       =    depths
							__lowerCamelCase		       =    num_heads
							__lowerCamelCase		       =    window_size
							__lowerCamelCase		       =    mlp_ratio
							__lowerCamelCase		       =    qkv_bias
							__lowerCamelCase		       =    hidden_dropout_prob
							__lowerCamelCase		       =    attention_probs_dropout_prob
							__lowerCamelCase		       =    drop_path_rate
							__lowerCamelCase		       =    hidden_act
							__lowerCamelCase		       =    use_absolute_embeddings
							__lowerCamelCase		       =    patch_norm
							__lowerCamelCase		       =    layer_norm_eps
							__lowerCamelCase		       =    initializer_range
							__lowerCamelCase		       =    is_training
							__lowerCamelCase		       =    scope
							__lowerCamelCase		       =    use_labels
							__lowerCamelCase		       =    type_sequence_label_size
							__lowerCamelCase		       =    encoder_stride
							__lowerCamelCase		       =    out_features
							__lowerCamelCase		       =    out_indices


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



							'''simple docstring'''
							__lowerCamelCase		       =    floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]							)

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

							__lowerCamelCase		       =    self.get_config()

							return config, pixel_values, labels


			def       lowercase_    (      self							)    ->      List[str]:



							'''simple docstring'''
							return FocalNetConfig(
							    image_size=self.image_size			,						patch_size=self.patch_size			,						num_channels=self.num_channels			,						embed_dim=self.embed_dim			,						hidden_sizes=self.hidden_sizes			,						depths=self.depths			,						num_heads=self.num_heads			,						window_size=self.window_size			,						mlp_ratio=self.mlp_ratio			,						qkv_bias=self.qkv_bias			,						hidden_dropout_prob=self.hidden_dropout_prob			,						attention_probs_dropout_prob=self.attention_probs_dropout_prob			,						drop_path_rate=self.drop_path_rate			,						hidden_act=self.hidden_act			,						use_absolute_embeddings=self.use_absolute_embeddings			,						path_norm=self.patch_norm			,						layer_norm_eps=self.layer_norm_eps			,						initializer_range=self.initializer_range			,						encoder_stride=self.encoder_stride			,						out_features=self.out_features			,						out_indices=self.out_indices			,						)


			def       lowercase_    (      self			,						lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__							)    ->      int:



							'''simple docstring'''
							__lowerCamelCase		       =    FocalNetModel(config=lowerCamelCase__							)
							model.to(lowerCamelCase__							)
							model.eval()
							__lowerCamelCase		       =    model(lowerCamelCase__							)

							__lowerCamelCase		       =    ((config.image_size // config.patch_size) ** 2) // (4 ** (len(config.depths							) - 1))
							__lowerCamelCase		       =    int(config.embed_dim * 2 ** (len(config.depths							) - 1)							)

							self.parent.assertEqual(result.last_hidden_state.shape			,						(self.batch_size, expected_seq_len, expected_dim)							)


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



							'''simple docstring'''
							__lowerCamelCase		       =    FocalNetBackbone(config=lowerCamelCase__							)
							model.to(lowerCamelCase__							)
							model.eval()
							__lowerCamelCase		       =    model(lowerCamelCase__							)

							# verify feature maps
							self.parent.assertEqual(len(result.feature_maps							)			,						len(config.out_features							)							)
							self.parent.assertListEqual(list(result.feature_maps[0].shape							)			,						[self.batch_size, self.image_size, 8, 8]							)

							# verify channels
							self.parent.assertEqual(len(model.channels							)			,						len(config.out_features							)							)
							self.parent.assertListEqual(model.channels			,						config.hidden_sizes[:-1]							)

							# verify backbone works with out_features=None
							__lowerCamelCase		       =    None
							__lowerCamelCase		       =    FocalNetBackbone(config=lowerCamelCase__							)
							model.to(lowerCamelCase__							)
							model.eval()
							__lowerCamelCase		       =    model(lowerCamelCase__							)

							# verify feature maps
							self.parent.assertEqual(len(result.feature_maps							)			,						1							)
							self.parent.assertListEqual(list(result.feature_maps[0].shape							)			,						[self.batch_size, self.image_size * 2, 4, 4]							)

							# verify channels
							self.parent.assertEqual(len(model.channels							)			,						1							)
							self.parent.assertListEqual(model.channels			,						[config.hidden_sizes[-1]]							)


			def       lowercase_    (      self			,						lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__							)    ->      int:



							'''simple docstring'''
							__lowerCamelCase		       =    FocalNetForMaskedImageModeling(config=lowerCamelCase__							)
							model.to(lowerCamelCase__							)
							model.eval()
							__lowerCamelCase		       =    model(lowerCamelCase__							)
							self.parent.assertEqual(
							    result.reconstruction.shape			,						(self.batch_size, self.num_channels, self.image_size, self.image_size)							)

							# test greyscale images
							__lowerCamelCase		       =    1
							__lowerCamelCase		       =    FocalNetForMaskedImageModeling(lowerCamelCase__							)
							model.to(lowerCamelCase__							)
							model.eval()

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


			def       lowercase_    (      self			,						lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__							)    ->      str:



							'''simple docstring'''
							__lowerCamelCase		       =    self.type_sequence_label_size
							__lowerCamelCase		       =    FocalNetForImageClassification(lowerCamelCase__							)
							model.to(lowerCamelCase__							)
							model.eval()
							__lowerCamelCase		       =    model(lowerCamelCase__			,						labels=lowerCamelCase__							)
							self.parent.assertEqual(result.logits.shape			,						(self.batch_size, self.type_sequence_label_size)							)

							# test greyscale images
							__lowerCamelCase		       =    1
							__lowerCamelCase		       =    FocalNetForImageClassification(lowerCamelCase__							)
							model.to(lowerCamelCase__							)
							model.eval()

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






			def       lowercase_    (      self							)    ->      Tuple:



							'''simple docstring'''
							__lowerCamelCase		       =    self.prepare_config_and_inputs()

							__lowerCamelCase       ,						__lowerCamelCase       ,						__lowerCamelCase		       =    config_and_inputs
							__lowerCamelCase		       =    {'pixel_values': pixel_values}
							return config, inputs_dict







@require_torch
class     __lowerCAmelCase (       __magic_name__			,				__magic_name__			,				unittest.TestCase ):

			"""simple docstring"""







			snake_case_   		=       (
			    (
			        FocalNetModel,
			        FocalNetForImageClassification,
			        FocalNetForMaskedImageModeling,
			        FocalNetBackbone,
			    )
			    if is_torch_available()
			    else ()
			)
			snake_case_   		=       (
			    {'''feature-extraction''': FocalNetModel, '''image-classification''': FocalNetForImageClassification}
			    if is_torch_available()
			    else {}
			)
			snake_case_   		=       False

			snake_case_   		=       False
			snake_case_   		=       False
			snake_case_   		=       False
			snake_case_   		=       False


			def       lowercase_    (      self							)    ->      str:



							'''simple docstring'''
							__lowerCamelCase		       =    FocalNetModelTester(self							)
							__lowerCamelCase		       =    ConfigTester(self			,						config_class=lowerCamelCase__			,						embed_dim=37			,						has_text_modality=lowerCamelCase__							)


			def       lowercase_    (      self							)    ->      str:



							'''simple docstring'''
							self.create_and_test_config_common_properties()
							self.config_tester.create_and_test_config_to_json_string()
							self.config_tester.create_and_test_config_to_json_file()
							self.config_tester.create_and_test_config_from_and_save_pretrained()
							self.config_tester.create_and_test_config_with_num_labels()
							self.config_tester.check_config_can_be_init_without_params()
							self.config_tester.check_config_arguments_init()


			def       lowercase_    (      self							)    ->      str:



							'''simple docstring'''
							return


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



							'''simple docstring'''
							__lowerCamelCase		       =    self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_model(*lowerCamelCase__							)


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



							'''simple docstring'''
							__lowerCamelCase		       =    self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_backbone(*lowerCamelCase__							)


			def       lowercase_    (      self							)    ->      str:



							'''simple docstring'''
							__lowerCamelCase		       =    self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_masked_image_modeling(*lowerCamelCase__							)


			def       lowercase_    (      self							)    ->      Any:



							'''simple docstring'''
							__lowerCamelCase		       =    self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_image_classification(*lowerCamelCase__							)


			@unittest.skip(reason='FocalNet does not use inputs_embeds'							)
			def       lowercase_    (      self							)    ->      Optional[int]:



							'''simple docstring'''
							pass


			@unittest.skip(reason='FocalNet does not use feedforward chunking'							)
			def       lowercase_    (      self							)    ->      Union[str, Any]:



							'''simple docstring'''
							pass


			def       lowercase_    (      self							)    ->      Dict:



							'''simple docstring'''
							__lowerCamelCase       ,						__lowerCamelCase		       =    self.model_tester.prepare_config_and_inputs_for_common()

							for model_class in self.all_model_classes[:-1]:
											__lowerCamelCase		       =    model_class(lowerCamelCase__							)
											self.assertIsInstance(model.get_input_embeddings()			,						(nn.Module)							)
											__lowerCamelCase		       =    model.get_output_embeddings()
											self.assertTrue(x is None or isinstance(lowerCamelCase__			,						nn.Linear							)							)


			def       lowercase_    (      self							)    ->      str:



							'''simple docstring'''
							__lowerCamelCase       ,						__lowerCamelCase		       =    self.model_tester.prepare_config_and_inputs_for_common()

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

											__lowerCamelCase		       =    ['pixel_values']
											self.assertListEqual(arg_names[:1]			,						lowerCamelCase__							)


			def       lowercase_    (      self			,						lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__							)    ->      int:



							'''simple docstring'''
							__lowerCamelCase		       =    model_class(lowerCamelCase__							)
							model.to(lowerCamelCase__							)
							model.eval()

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

							__lowerCamelCase		       =    outputs.hidden_states

							__lowerCamelCase		       =    getattr(
							    self.model_tester			,						'expected_num_hidden_layers'			,						len(self.model_tester.depths							) + 1							)
							self.assertEqual(len(lowerCamelCase__							)			,						lowerCamelCase__							)

							# FocalNet has a different seq_length
							__lowerCamelCase		       =    (
							    config.patch_size
							    if isinstance(config.patch_size			,						collections.abc.Iterable							)
							    else (config.patch_size, config.patch_size)
							)

							__lowerCamelCase		       =    (image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])

							self.assertListEqual(
							    list(hidden_states[0].shape[-2:]							)			,						[num_patches, self.model_tester.embed_dim]			,						)

							__lowerCamelCase		       =    outputs.reshaped_hidden_states
							self.assertEqual(len(lowerCamelCase__							)			,						lowerCamelCase__							)

							__lowerCamelCase       ,						__lowerCamelCase       ,						__lowerCamelCase       ,						__lowerCamelCase		       =    reshaped_hidden_states[0].shape
							__lowerCamelCase		       =    (
							    reshaped_hidden_states[0].view(lowerCamelCase__			,						lowerCamelCase__			,						height * width							).permute(0			,						2			,						1							)
							)
							self.assertListEqual(
							    list(reshaped_hidden_states.shape[-2:]							)			,						[num_patches, self.model_tester.embed_dim]			,						)


			def       lowercase_    (      self							)    ->      Dict:



							'''simple docstring'''
							__lowerCamelCase       ,						__lowerCamelCase		       =    self.model_tester.prepare_config_and_inputs_for_common()

							__lowerCamelCase		       =    (
							    self.model_tester.image_size
							    if isinstance(self.model_tester.image_size			,						collections.abc.Iterable							)
							    else (self.model_tester.image_size, self.model_tester.image_size)
							)

							for model_class in self.all_model_classes[:-1]:
											__lowerCamelCase		       =    True
											self.check_hidden_states_output(lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__							)

											# check that output_hidden_states also work using config
											del inputs_dict["output_hidden_states"]
											__lowerCamelCase		       =    True

											self.check_hidden_states_output(lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__							)


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



							'''simple docstring'''
							__lowerCamelCase       ,						__lowerCamelCase		       =    self.model_tester.prepare_config_and_inputs_for_common()
							__lowerCamelCase		       =    3

							__lowerCamelCase		       =    (
							    self.model_tester.image_size
							    if isinstance(self.model_tester.image_size			,						collections.abc.Iterable							)
							    else (self.model_tester.image_size, self.model_tester.image_size)
							)
							__lowerCamelCase		       =    (
							    config.patch_size
							    if isinstance(config.patch_size			,						collections.abc.Iterable							)
							    else (config.patch_size, config.patch_size)
							)

							__lowerCamelCase		       =    image_size[0] + patch_size[0] - (image_size[0] % patch_size[0])
							__lowerCamelCase		       =    image_size[1] + patch_size[1] - (image_size[1] % patch_size[1])

							for model_class in self.all_model_classes[:-1]:
											__lowerCamelCase		       =    True
											self.check_hidden_states_output(lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__			,						(padded_height, padded_width)							)

											# check that output_hidden_states also work using config
											del inputs_dict["output_hidden_states"]
											__lowerCamelCase		       =    True
											self.check_hidden_states_output(lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__			,						(padded_height, padded_width)							)


			@slow
			def       lowercase_    (      self							)    ->      str:



							'''simple docstring'''
							for model_name in FOCALNET_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
											__lowerCamelCase		       =    FocalNetModel.from_pretrained(lowerCamelCase__							)
											self.assertIsNotNone(lowerCamelCase__							)






			def       lowercase_    (      self							)    ->      Optional[int]:



							'''simple docstring'''
							__lowerCamelCase       ,						__lowerCamelCase		       =    self.model_tester.prepare_config_and_inputs_for_common()

							__lowerCamelCase		       =    _config_zero_init(lowerCamelCase__							)
							for model_class in self.all_model_classes:
											__lowerCamelCase		       =    model_class(config=lowerCamelCase__							)
											for name, param in model.named_parameters():
															if "embeddings" not in name and param.requires_grad:
																			self.assertIn(
																			    ((param.data.mean() * 1e9).round() / 1e9).item()			,						[0.0, 1.0]			,						msg=f"""Parameter {name} of model {model_class} seems not properly initialized"""			,						)







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

			"""simple docstring"""







			@cached_property
			def       lowercase_    (      self							)    ->      List[str]:



							'''simple docstring'''
							# TODO update organization
							return AutoImageProcessor.from_pretrained('microsoft/focalnet-tiny'							) if is_vision_available() else None






			@slow
			def       lowercase_    (      self							)    ->      List[Any]:



							'''simple docstring'''
							__lowerCamelCase		       =    FocalNetForImageClassification.from_pretrained('microsoft/focalnet-tiny'							).to(lowerCamelCase__							)
							__lowerCamelCase		       =    self.default_image_processor

							__lowerCamelCase		       =    Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png'							)
							__lowerCamelCase		       =    image_processor(images=lowerCamelCase__			,						return_tensors='pt'							).to(lowerCamelCase__							)

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

							# verify the logits
							__lowerCamelCase		       =    torch.Size((1, 1_000)							)
							self.assertEqual(outputs.logits.shape			,						lowerCamelCase__							)
							__lowerCamelCase		       =    torch.tensor([0.21_66, -0.43_68, 0.21_91]							).to(lowerCamelCase__							)
							self.assertTrue(torch.allclose(outputs.logits[0, :3]			,						lowerCamelCase__			,						atol=1e-4							)							)
							self.assertTrue(outputs.logits.argmax(dim=-1							).item()			,						281							)







@require_torch
class     __lowerCAmelCase (       __magic_name__			,				unittest.TestCase ):

			"""simple docstring"""







			snake_case_   		=       (FocalNetBackbone,) if is_torch_available() else ()
			snake_case_   		=       FocalNetConfig

			snake_case_   		=       False


			def       lowercase_    (      self							)    ->      Any:



							'''simple docstring'''
							__lowerCamelCase		       =    FocalNetModelTester(self							)


