






'''simple docstring'''





import copy
import inspect
import unittest

import numpy as np
from huggingface_hub import hf_hub_download

from transformers import TimesformerConfig
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 torch import nn

						from transformers import (
						    MODEL_FOR_VIDEO_CLASSIFICATION_MAPPING,
						    TimesformerForVideoClassification,
						    TimesformerModel,
						)
						from transformers.models.timesformer.modeling_timesformer import TIMESFORMER_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
						from transformers import VideoMAEImageProcessor


class  snake_case__      :




					def __init__(  self  :		Optional[Any]				, _A  :		List[Any]				, _A  :		Union[str, Any]=13				, _A  :		List[Any]=10				, _A  :		Optional[int]=3				, _A  :		Optional[Any]=2				, _A  :		int=2				, _A  :		Optional[Any]=True				, _A  :		str=True				, _A  :		int=32				, _A  :		Tuple=5				, _A  :		Union[str, Any]=4				, _A  :		Tuple=37				, _A  :		Tuple="gelu"				, _A  :		Union[str, Any]=0.1				, _A  :		List[str]=0.1				, _A  :		List[Any]=10				, _A  :		Optional[int]=0.02				, _A  :		Union[str, Any]="divided_space_time"				, _A  :		Dict=None				, )    ->							Any:
								UpperCAmelCase_      :       str          =       parent
								UpperCAmelCase_      :       Optional[int]          =       batch_size
								UpperCAmelCase_      :       List[Any]          =       image_size
								UpperCAmelCase_      :       Union[str, Any]          =       num_channels
								UpperCAmelCase_      :       List[str]          =       patch_size
								UpperCAmelCase_      :       Dict          =       num_frames
								UpperCAmelCase_      :       List[str]          =       is_training
								UpperCAmelCase_      :       List[Any]          =       use_labels
								UpperCAmelCase_      :       Tuple          =       hidden_size
								UpperCAmelCase_      :       List[str]          =       num_hidden_layers
								UpperCAmelCase_      :       Union[str, Any]          =       num_attention_heads
								UpperCAmelCase_      :       List[Any]          =       intermediate_size
								UpperCAmelCase_      :       Union[str, Any]          =       hidden_act
								UpperCAmelCase_      :       Optional[int]          =       hidden_dropout_prob
								UpperCAmelCase_      :       Optional[Any]          =       attention_probs_dropout_prob
								UpperCAmelCase_      :       List[Any]          =       attention_type
								UpperCAmelCase_      :       Union[str, Any]          =       initializer_range
								UpperCAmelCase_      :       str          =       scope
								UpperCAmelCase_      :       List[str]          =       num_labels

								# in TimeSformer, the number of spatial tokens equals num_frames * num_patches per frame + 1 CLS token
								UpperCAmelCase_      :       Optional[int]          =       (image_size // patch_size) ** 2
								UpperCAmelCase_      :       Any          =       (num_frames) * self.num_patches_per_frame + 1




					def 		A      (  self  :		List[str]      )    ->							Tuple:
								UpperCAmelCase_      :       Dict          =       floats_tensor(
								    [self.batch_size, self.num_frames, self.num_channels, self.image_size, self.image_size]      )

								UpperCAmelCase_      :       Any          =       None
								if self.use_labels:
											UpperCAmelCase_      :       Dict          =       ids_tensor([self.batch_size]				, self.num_labels      )

								UpperCAmelCase_      :       Dict          =       self.get_config()

								return config, pixel_values, labels




					def 		A      (  self  :		int      )    ->							Any:
								UpperCAmelCase_      :       List[Any]          =       TimesformerConfig(
								    image_size=self.image_size				, patch_size=self.patch_size				, num_channels=self.num_channels				, num_frames=self.num_frames				, 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				, initializer_range=self.initializer_range				, attention_type=self.attention_type				, )
								UpperCAmelCase_      :       Tuple          =       self.num_labels
								return config




					def 		A      (  self  :		str				, _A  :		int				, _A  :		str				, _A  :		Optional[Any]      )    ->							int:
								UpperCAmelCase_      :       List[Any]          =       TimesformerModel(config=_A      )
								model.to(_A      )
								model.eval()
								UpperCAmelCase_      :       int          =       model(_A      )
								self.parent.assertEqual(result.last_hidden_state.shape				, (self.batch_size, self.seq_length, self.hidden_size)      )




					def 		A      (  self  :		Optional[int]				, _A  :		int				, _A  :		Optional[int]				, _A  :		int      )    ->							str:
								UpperCAmelCase_      :       List[Any]          =       TimesformerForVideoClassification(_A      )
								model.to(_A      )
								model.eval()

								UpperCAmelCase_      :       Tuple          =       model(_A      )

								# verify the logits shape
								UpperCAmelCase_      :       Tuple          =       torch.Size((self.batch_size, self.num_labels)      )
								self.parent.assertEqual(result.logits.shape				, _A      )





					def 		A      (  self  :		Dict      )    ->							str:
								UpperCAmelCase_      :       Dict          =       self.prepare_config_and_inputs()
								UpperCAmelCase_    ,      UpperCAmelCase_    ,      UpperCAmelCase_      :       List[Any]          =       config_and_inputs
								UpperCAmelCase_      :       Any          =       {'''pixel_values''': pixel_values}
								return config, inputs_dict






@require_torch
class  snake_case__      (					UpperCamelCase     ,				UpperCamelCase     ,				unittest.TestCase):
					a_        =					(TimesformerModel, TimesformerForVideoClassification) if is_torch_available() else ()
					a_        =					(
					    {"feature-extraction": TimesformerModel, "video-classification": TimesformerForVideoClassification}
					    if is_torch_available()
					    else {}
					)

					a_        =					False
					a_        =					False
					a_        =					False
					a_        =					False




					def 		A      (  self  :		Tuple      )    ->							str:
								UpperCAmelCase_      :       Union[str, Any]          =       TimesformerModelTester(self      )
								UpperCAmelCase_      :       Any          =       ConfigTester(
								    self				, config_class=_A				, has_text_modality=_A				, hidden_size=37      )




					def 		A      (  self  :		Union[str, Any]				, _A  :		str				, _A  :		Dict				, _A  :		str=False      )    ->							Optional[Any]:
								UpperCAmelCase_      :       int          =       copy.deepcopy(_A      )

								if return_labels:
											if model_class in get_values(_A      ):
														UpperCAmelCase_      :       Any          =       torch.zeros(
														    self.model_tester.batch_size				, dtype=torch.long				, device=_A      )

								return inputs_dict




					def 		A      (  self  :		Union[str, Any]      )    ->							Union[str, Any]:
								self.config_tester.run_common_tests()




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




					def 		A      (  self  :		Tuple      )    ->							Optional[int]:
								UpperCAmelCase_    ,      UpperCAmelCase_      :       Dict          =       self.model_tester.prepare_config_and_inputs_for_common()

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




					def 		A      (  self  :		Tuple      )    ->							Union[str, Any]:
								UpperCAmelCase_    ,      UpperCAmelCase_      :       Optional[int]          =       self.model_tester.prepare_config_and_inputs_for_common()

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

											UpperCAmelCase_      :       Dict          =       ['''pixel_values''']
											self.assertListEqual(arg_names[:1]				, _A      )




					def 		A      (  self  :		List[Any]      )    ->							List[str]:
								UpperCAmelCase_      :       List[str]          =       self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_model(*_A      )




					def 		A      (  self  :		Optional[int]      )    ->							Dict:
								UpperCAmelCase_      :       str          =       self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_for_video_classification(*_A      )




					@slow
					def 		A      (  self  :		Optional[int]      )    ->							List[str]:
								for model_name in TIMESFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
											UpperCAmelCase_      :       Any          =       TimesformerModel.from_pretrained(_A      )
											self.assertIsNotNone(_A      )




					def 		A      (  self  :		Optional[Any]      )    ->							Union[str, Any]:
								if not self.has_attentions:
											pass

								else:
											UpperCAmelCase_    ,      UpperCAmelCase_      :       Union[str, Any]          =       self.model_tester.prepare_config_and_inputs_for_common()
											UpperCAmelCase_      :       int          =       True

											for model_class in self.all_model_classes:
														UpperCAmelCase_      :       List[str]          =       self.model_tester.seq_length
														UpperCAmelCase_      :       Tuple          =       self.model_tester.num_frames

														UpperCAmelCase_      :       Union[str, Any]          =       True
														UpperCAmelCase_      :       str          =       False
														UpperCAmelCase_      :       Optional[int]          =       True
														UpperCAmelCase_      :       Any          =       model_class(_A      )
														model.to(_A      )
														model.eval()
														with torch.no_grad():
																	UpperCAmelCase_      :       Tuple          =       model(**self._prepare_for_class(_A				, _A      )      )
														UpperCAmelCase_      :       Optional[Any]          =       outputs.attentions
														self.assertEqual(len(_A      )				, self.model_tester.num_hidden_layers      )

														# check that output_attentions also work using config
														del inputs_dict["output_attentions"]
														UpperCAmelCase_      :       Optional[Any]          =       True
														UpperCAmelCase_      :       Optional[int]          =       model_class(_A      )
														model.to(_A      )
														model.eval()
														with torch.no_grad():
																	UpperCAmelCase_      :       Optional[int]          =       model(**self._prepare_for_class(_A				, _A      )      )
														UpperCAmelCase_      :       Any          =       outputs.attentions
														self.assertEqual(len(_A      )				, self.model_tester.num_hidden_layers      )

														# attentions has shape (batch_size x num_frames) x num_heads x (num_patches per frame + 1) x (num_patches per frame + 1)
														self.assertListEqual(
														    list(attentions[0].shape[-3:]      )				, [self.model_tester.num_attention_heads, seq_len // num_frames + 1, seq_len // num_frames + 1]				, )
														UpperCAmelCase_      :       str          =       len(_A      )

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

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

														UpperCAmelCase_      :       int          =       outputs.attentions

														self.assertEqual(len(_A      )				, self.model_tester.num_hidden_layers      )

														# attentions has shape (batch_size x num_frames) x num_heads x (num_patches per frame + 1) x (num_patches per frame + 1)
														self.assertListEqual(
														    list(self_attentions[0].shape[-3:]      )				, [self.model_tester.num_attention_heads, seq_len // num_frames + 1, seq_len // num_frames + 1]				, )





					def 		A      (  self  :		Dict      )    ->							Union[str, Any]:
								def check_hidden_states_output(_A  :		Union[str, Any]				, _A  :		str				, _A  :		int      ):
											UpperCAmelCase_      :       Tuple          =       model_class(_A      )
											model.to(_A      )
											model.eval()

											with torch.no_grad():
														UpperCAmelCase_      :       Optional[int]          =       model(**self._prepare_for_class(_A				, _A      )      )

											UpperCAmelCase_      :       Any          =       outputs.hidden_states
											UpperCAmelCase_      :       List[str]          =       self.model_tester.num_hidden_layers + 1
											self.assertEqual(len(_A      )				, _A      )

											UpperCAmelCase_      :       Tuple          =       self.model_tester.seq_length

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

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

								for model_class in self.all_model_classes:
											UpperCAmelCase_      :       Tuple          =       True
											check_hidden_states_output(_A				, _A				, _A      )

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

											check_hidden_states_output(_A				, _A				, _A      )






def __UpperCAmelCase   (					)    ->   List[str]:
			UpperCAmelCase_      :       Optional[int]          =       hf_hub_download(
			    repo_id='''hf-internal-testing/spaghetti-video'''			,       filename='''eating_spaghetti.npy'''			,       repo_type='''dataset'''		)
			UpperCAmelCase_      :       str          =       np.load(A		)
			return list(A		)







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




					@cached_property
					def 		A      (  self  :		Tuple      )    ->							Tuple:
								# logits were tested with a different mean and std, so we use the same here
								return (
								    VideoMAEImageProcessor(image_mean=[0.5, 0.5, 0.5]				, image_std=[0.5, 0.5, 0.5]      )
								    if is_vision_available()
								    else None
								)





					@slow
					def 		A      (  self  :		Tuple      )    ->							str:
								UpperCAmelCase_      :       List[str]          =       TimesformerForVideoClassification.from_pretrained('''facebook/timesformer-base-finetuned-k400'''      ).to(
								    _A      )

								UpperCAmelCase_      :       List[str]          =       self.default_image_processor
								UpperCAmelCase_      :       Union[str, Any]          =       prepare_video()
								UpperCAmelCase_      :       Any          =       image_processor(video[:8]				, return_tensors='''pt'''      ).to(_A      )

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

								# verify the logits
								UpperCAmelCase_      :       Union[str, Any]          =       torch.Size((1, 4_00)      )
								self.assertEqual(outputs.logits.shape				, _A      )

								UpperCAmelCase_      :       str          =       torch.tensor([-0.3_016, -0.7_713, -0.4_205]      ).to(_A      )

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










'''simple docstring'''





def __UpperCAmelCase   (					A					:			list		)    ->   list:
			if len(A		) <= 1:
						return lst

			UpperCAmelCase_      :       List[str]          =       1

			while i < len(A		):
						if lst[i - 1] <= lst[i]:
									i += 1
						else:
									UpperCAmelCase_    ,      UpperCAmelCase_      :       Dict          =       lst[i], lst[i - 1]
									i -= 1
									if i == 0:
												UpperCAmelCase_      :       Dict          =       1

			return lst


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


