
"""simple docstring"""
import collections
import inspect
import unittest

from transformers import DonutSwinConfig
from transformers.testing_utils import require_torch, slow, torch_device
from transformers.utils import is_torch_available

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 DonutSwinModel
			from transformers.models.donut.modeling_donut_swin import DONUT_SWIN_PRETRAINED_MODEL_ARCHIVE_LIST
class      lowerCAmelCase_						:



							'''simple docstring'''





							def __init__(				self  ,							snake_case_  ,							snake_case_=13  ,							snake_case_=32  ,							snake_case_=2  ,							snake_case_=3  ,							snake_case_=16  ,							snake_case_=[1, 2, 1]  ,							snake_case_=[2, 2, 4]  ,							snake_case_=2  ,							snake_case_=2.0  ,							snake_case_=True  ,							snake_case_=0.0  ,							snake_case_=0.0  ,							snake_case_=0.1  ,							snake_case_="gelu"  ,							snake_case_=False  ,							snake_case_=True  ,							snake_case_=0.02  ,							snake_case_=1e-5  ,							snake_case_=True  ,							snake_case_=None  ,							snake_case_=True  ,							snake_case_=10  ,							snake_case_=8  ,							)   ->       Union[str, Any]:
													__lowerCAmelCase        =       parent
													__lowerCAmelCase        =       batch_size
													__lowerCAmelCase        =       image_size
													__lowerCAmelCase        =       patch_size
													__lowerCAmelCase        =       num_channels
													__lowerCAmelCase        =       embed_dim
													__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




							def  A__		(				self							)   ->       Union[str, Any]:
													__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  A__		(				self							)   ->       List[str]:
													return DonutSwinConfig(
													    image_size=self.image_size  ,							patch_size=self.patch_size  ,							num_channels=self.num_channels  ,							embed_dim=self.embed_dim  ,							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  ,							)




							def  A__		(				self  ,							snake_case_  ,							snake_case_  ,							snake_case_							)   ->       Union[str, Any]:
													__lowerCAmelCase        =       DonutSwinModel(config=snake_case_							)
													model.to(snake_case_							)
													model.eval()
													__lowerCAmelCase        =       model(snake_case_							)

													__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  A__		(				self							)   ->       Dict:
													__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_						(							A__							,							A__							,							unittest.TestCase				):



							'''simple docstring'''





							_snake_case		     =						(DonutSwinModel,) if is_torch_available() else ()
							_snake_case		     =						{'''feature-extraction''': DonutSwinModel} if is_torch_available() else {}
							_snake_case		     =						True

							_snake_case		     =						False
							_snake_case		     =						False
							_snake_case		     =						False




							def  A__		(				self							)   ->       List[Any]:
													__lowerCAmelCase        =       DonutSwinModelTester(self							)
													__lowerCAmelCase        =       ConfigTester(self  ,							config_class=snake_case_  ,							embed_dim=37							)




							def  A__		(				self							)   ->       str:
													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  A__		(				self							)   ->       Dict:
													return




							def  A__		(				self							)   ->       Optional[Any]:
													__lowerCAmelCase        =       self.model_tester.prepare_config_and_inputs()
													self.model_tester.create_and_check_model(*snake_case_							)




							def  A__		(				self							)   ->       List[str]:
													# DonutSwin does not use inputs_embeds
													pass




							def  A__		(				self							)   ->       str:
													__lowerCAmelCase ,      __lowerCAmelCase        =       self.model_tester.prepare_config_and_inputs_for_common()

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




							def  A__		(				self							)   ->       Union[str, Any]:
													__lowerCAmelCase ,      __lowerCAmelCase        =       self.model_tester.prepare_config_and_inputs_for_common()

													for model_class in self.all_model_classes:
																			__lowerCAmelCase        =       model_class(snake_case_							)
																			__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]  ,							snake_case_							)




							def  A__		(				self							)   ->       Tuple:
													__lowerCAmelCase ,      __lowerCAmelCase        =       self.model_tester.prepare_config_and_inputs_for_common()
													__lowerCAmelCase        =       True

													for model_class in self.all_model_classes:
																			__lowerCAmelCase        =       True
																			__lowerCAmelCase        =       False
																			__lowerCAmelCase        =       True
																			__lowerCAmelCase        =       model_class(snake_case_							)
																			model.to(snake_case_							)
																			model.eval()
																			with torch.no_grad():
																									__lowerCAmelCase        =       model(**self._prepare_for_class(snake_case_  ,							snake_case_							)							)
																			__lowerCAmelCase        =       outputs.attentions
																			__lowerCAmelCase        =       len(self.model_tester.depths							)
																			self.assertEqual(len(snake_case_							)  ,							snake_case_							)

																			# check that output_attentions also work using config
																			del inputs_dict["output_attentions"]
																			__lowerCAmelCase        =       True
																			__lowerCAmelCase        =       config.window_size**2
																			__lowerCAmelCase        =       model_class(snake_case_							)
																			model.to(snake_case_							)
																			model.eval()
																			with torch.no_grad():
																									__lowerCAmelCase        =       model(**self._prepare_for_class(snake_case_  ,							snake_case_							)							)
																			__lowerCAmelCase        =       outputs.attentions
																			self.assertEqual(len(snake_case_							)  ,							snake_case_							)

																			self.assertListEqual(
																			    list(attentions[0].shape[-3:]							)  ,							[self.model_tester.num_heads[0], window_size_squared, window_size_squared]  ,							)
																			__lowerCAmelCase        =       len(snake_case_							)

																			# Check attention is always last and order is fine
																			__lowerCAmelCase        =       True
																			__lowerCAmelCase        =       True
																			__lowerCAmelCase        =       model_class(snake_case_							)
																			model.to(snake_case_							)
																			model.eval()
																			with torch.no_grad():
																									__lowerCAmelCase        =       model(**self._prepare_for_class(snake_case_  ,							snake_case_							)							)

																			if hasattr(self.model_tester  ,							"""num_hidden_states_types"""							):
																									__lowerCAmelCase        =       self.model_tester.num_hidden_states_types
																			else:
																									# also another +1 for reshaped_hidden_states
																									__lowerCAmelCase        =       2
																			self.assertEqual(out_len + added_hidden_states  ,							len(snake_case_							)							)

																			__lowerCAmelCase        =       outputs.attentions

																			self.assertEqual(len(snake_case_							)  ,							snake_case_							)

																			self.assertListEqual(
																			    list(self_attentions[0].shape[-3:]							)  ,							[self.model_tester.num_heads[0], window_size_squared, window_size_squared]  ,							)




							def  A__		(				self  ,							snake_case_  ,							snake_case_  ,							snake_case_  ,							snake_case_							)   ->       Optional[Any]:
													__lowerCAmelCase        =       model_class(snake_case_							)
													model.to(snake_case_							)
													model.eval()

													with torch.no_grad():
																			__lowerCAmelCase        =       model(**self._prepare_for_class(snake_case_  ,							snake_case_							)							)

													__lowerCAmelCase        =       outputs.hidden_states

													__lowerCAmelCase        =       getattr(
													    self.model_tester  ,							"""expected_num_hidden_layers"""  ,							len(self.model_tester.depths							) + 1							)
													self.assertEqual(len(snake_case_							)  ,							snake_case_							)

													# DonutSwin 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(snake_case_							)  ,							snake_case_							)

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




							def  A__		(				self							)   ->       List[Any]:
													__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:
																			__lowerCAmelCase        =       True
																			self.check_hidden_states_output(snake_case_  ,							snake_case_  ,							snake_case_  ,							snake_case_							)

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

																			self.check_hidden_states_output(snake_case_  ,							snake_case_  ,							snake_case_  ,							snake_case_							)




							def  A__		(				self							)   ->       str:
													__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:
																			__lowerCAmelCase        =       True
																			self.check_hidden_states_output(snake_case_  ,							snake_case_  ,							snake_case_  ,							(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(snake_case_  ,							snake_case_  ,							snake_case_  ,							(padded_height, padded_width)							)




							@slow
							def  A__		(				self							)   ->       str:
													for model_name in DONUT_SWIN_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																			__lowerCAmelCase        =       DonutSwinModel.from_pretrained(snake_case_							)
																			self.assertIsNotNone(snake_case_							)




							def  A__		(				self							)   ->       int:
													__lowerCAmelCase ,      __lowerCAmelCase        =       self.model_tester.prepare_config_and_inputs_for_common()

													__lowerCAmelCase        =       _config_zero_init(snake_case_							)
													for model_class in self.all_model_classes:
																			__lowerCAmelCase        =       model_class(config=snake_case_							)
																			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"""  ,							)


"""simple docstring"""
from __future__ import annotations
class      lowerCAmelCase_						:



							'''simple docstring'''





							def __init__(				self  ,							snake_case_							)   ->       None:
													__lowerCAmelCase        =       data
													__lowerCAmelCase        =       None
class      lowerCAmelCase_						:



							'''simple docstring'''





							def __init__(				self							)   ->       List[str]:
													__lowerCAmelCase        =       None




							def  A__		(				self  ,							snake_case_							)   ->       int:
													__lowerCAmelCase        =       Node(snake_case_							)
													__lowerCAmelCase        =       self.head
													__lowerCAmelCase        =       new_node
													return self.head.data




							def  A__		(				self							)   ->       int | None:
													__lowerCAmelCase        =       self.head
													__lowerCAmelCase        =       self.head
													if self.head:
																			while fast_pointer and fast_pointer.next:
																									__lowerCAmelCase        =       fast_pointer.next.next
																									__lowerCAmelCase        =       slow_pointer.next
																			return slow_pointer.data
													else:
																			print("""No element found."""							)
																			return None


if __name__ == "__main__":
			SCREAMING_SNAKE_CASE_			      =					LinkedList()
			for _ in range(int(input().strip())):
						SCREAMING_SNAKE_CASE_			      =					int(input().strip())
						link.push(data)
			print(link.middle_element())
