

'''simple docstring'''

import importlib.util
import weakref
from functools import partialmethod

from .dependency_versions_check import dep_version_check
from .utils import is_accelerate_available, is_torch_available, logging


if is_torch_available():
				import torch

a       :      Any  	=			logging.get_logger(__name__)





def 				lowercase (					):



					'''simple docstring'''







					return importlib.util.find_spec("deepspeed"							) is not None


if is_accelerate_available() and is_deepspeed_available():
				from accelerate.utils.deepspeed import HfDeepSpeedConfig as DeepSpeedConfig
else:
				# Inherits from a dummy `object` if accelerate is not available, so that python succeeds to import this file.
				# Deepspeed glue code will never inherit this dummy object as it checks if accelerate is available.
				from builtins import object as DeepSpeedConfig







class   UpperCamelCase__   (       UpperCamelCase_       ):


		"""simple docstring"""

		def __init__(			self   ,      snake_case      ):


							'''simple docstring'''

							set_hf_deepspeed_config(self      )
							dep_version_check("accelerate"      )
							dep_version_check("deepspeed"      )
							super().__init__(__SCREAMING_SNAKE_CASE      )







class   UpperCamelCase__   (       UpperCamelCase_       ):


		"""simple docstring"""

		def __init__(			self   ,      snake_case      ):


							'''simple docstring'''

							super().__init__(__SCREAMING_SNAKE_CASE      )
							UpperCAmelCase		:							Optional[int]        =       None
							UpperCAmelCase		:							Any        =       []







		def 				A_	(			self      ):


							'''simple docstring'''

							if self._dtype is None:
												raise ValueError("trainer_config_process() wasn\'t called yet to tell dtype"      )
							return self._dtype







		def 				A_	(			self   ,      snake_case      ):


							'''simple docstring'''

							UpperCAmelCase		:							List[Any]        =       self.get_value(__SCREAMING_SNAKE_CASE      )
							if val is None:
												return False
							else:
												return val == "auto"







		def 				A_	(			self   ,      snake_case   ,      snake_case   ,      snake_case=None   ,      snake_case=True      ):


							'''simple docstring'''

							UpperCAmelCase ,			UpperCAmelCase		:							Optional[int]        =       self.find_config_node(__SCREAMING_SNAKE_CASE      )
							if config is None:
												return

							if config.get(__SCREAMING_SNAKE_CASE      ) == "auto":
												UpperCAmelCase		:							List[Any]        =       hf_val
												return

							if not must_match:
												return

							UpperCAmelCase		:							List[str]        =       config.get(__SCREAMING_SNAKE_CASE      )
							if ds_val is not None and ds_val != hf_val:
												self.mismatches.append(f"- ds {ds_key_long}={ds_val} vs hf {hf_key}={hf_val}"      )

		SCREAMING_SNAKE_CASE__  :     int       =							partialmethod(UpperCamelCase_							,							must_match=UpperCamelCase_       )







		def 				A_	(			self   ,      snake_case      ):


							'''simple docstring'''

							UpperCAmelCase		:							Dict        =       args.world_size * args.per_device_train_batch_size * args.gradient_accumulation_steps
							self.fill_match(
							    "train_micro_batch_size_per_gpu"   ,      args.per_device_train_batch_size   ,      "per_device_train_batch_size"      )
							self.fill_match("gradient_accumulation_steps"   ,      args.gradient_accumulation_steps   ,      "gradient_accumulation_steps"      )
							self.fill_match("train_batch_size"   ,      __SCREAMING_SNAKE_CASE   ,      "train_batch_size (calculated)"      )
							self.fill_match("gradient_clipping"   ,      args.max_grad_norm   ,      "max_grad_norm"      )

							self.fill_match("optimizer.params.lr"   ,      args.learning_rate   ,      "learning_rate"      )
							self.fill_match("optimizer.params.betas"   ,      [args.adam_betaa, args.adam_betaa]   ,      "adam_beta1+adam_beta2"      )
							self.fill_match("optimizer.params.eps"   ,      args.adam_epsilon   ,      "adam_epsilon"      )
							self.fill_match("optimizer.params.weight_decay"   ,      args.weight_decay   ,      "weight_decay"      )

							self.fill_only("scheduler.params.warmup_min_lr"   ,      0      )  # not a trainer arg
							self.fill_match("scheduler.params.warmup_max_lr"   ,      args.learning_rate   ,      "learning_rate"      )
							# total_num_steps - will get set in trainer_config_finalize

							# fp16
							if args.fpaa or args.fpaa_full_eval:
												UpperCAmelCase		:							Any        =       "apex" if args.fpaa_backend == "apex" else "amp"
							else:
												UpperCAmelCase		:							Tuple        =       None

							if args.save_on_each_node:
												# deepspeed uses shared storage by default. Let's override this setting if save_on_each_node == True
												UpperCAmelCase		:							Dict        =       self.config.get("checkpoint"   ,      {}      )
												UpperCAmelCase		:							int        =       args.save_on_each_node

							# amp: similar to the pytorch native amp - it has a bunch of optional params but we won't set
							# any here unless the user did the work
							self.fill_match(
							    "fp16.enabled"   ,      ((args.fpaa or args.fpaa_full_eval) and fpaa_backend == "amp")   ,      "fp16|fp16_full_eval+fp16_backend(amp)"   ,      )

							# apex: delegates amp work to apex (which needs to be available), but it cannot be used with any
							# ZeRO features
							self.fill_match("amp.enabled"   ,      fpaa_backend == "apex"   ,      "fp16+fp16_backend(apex)"      )
							self.fill_match("amp.opt_level"   ,      args.fpaa_opt_level   ,      "fp16_opt_level"      )

							self.fill_match("bf16.enabled"   ,      (args.bfaa or args.bfaa_full_eval)   ,      "bf16|bf16_full_eval"      )

							# deepspeed's default mode is fp16 unless there is a config that says differently
							if self.is_true("bf16.enabled"      ):
												UpperCAmelCase		:							List[Any]        =       torch.bfloataa
							elif self.is_false("fp16.enabled"      ):
												UpperCAmelCase		:							List[Any]        =       torch.floataa
							else:
												UpperCAmelCase		:							int        =       torch.floataa







		def 				A_	(			self   ,      snake_case   ,      snake_case   ,      snake_case      ):


							'''simple docstring'''

							UpperCAmelCase		:							Dict        =       [
							    "zero_optimization.reduce_bucket_size",
							    "zero_optimization.stage3_prefetch_bucket_size",
							    "zero_optimization.stage3_param_persistence_threshold",
							]
							UpperCAmelCase		:							Union[str, Any]        =       [x for x in hidden_size_based_keys if self.is_auto(__SCREAMING_SNAKE_CASE      )]

							if len(__SCREAMING_SNAKE_CASE      ) > 0:
												if hasattr(model.config   ,      "hidden_size"      ):
																	UpperCAmelCase		:							Tuple        =       model.config.hidden_size
												elif hasattr(model.config   ,      "hidden_sizes"      ):
																	# if there are many hidden sizes pick the largest one
																	UpperCAmelCase		:							List[Any]        =       max(model.config.hidden_sizes      )
												else:
																	raise ValueError(
																	    "The model\'s config file has neither `hidden_size` nor `hidden_sizes` entry, "
																	    "therefore it\'s not possible to automatically fill out the following `auto` entries "
																	    f"in the DeepSpeed config file: {hidden_size_auto_keys}. You can fix that by replacing "
																	    "`auto` values for these keys with an integer value of your choice."      )

												self.fill_only("zero_optimization.reduce_bucket_size"   ,      hidden_size * hidden_size      )
												if self.is_zeroa():
																	# automatically assign the optimal config values based on model config
																	self.fill_only("zero_optimization.stage3_prefetch_bucket_size"   ,      0.9 * hidden_size * hidden_size      )
																	self.fill_only("zero_optimization.stage3_param_persistence_threshold"   ,      1_0 * hidden_size      )

        # scheduler
							self.fill_match("scheduler.params.total_num_steps"   ,      __SCREAMING_SNAKE_CASE   ,      "num_training_steps (calculated)"      )
							self.fill_match("scheduler.params.warmup_num_steps"   ,      args.get_warmup_steps(__SCREAMING_SNAKE_CASE      )   ,      "warmup_steps"      )

							if len(self.mismatches      ) > 0:
												UpperCAmelCase		:							Any        =       "\n".join(self.mismatches      )
												raise ValueError(
												    "Please correct the following DeepSpeed config values that mismatch TrainingArguments"
												    f" values:\n{mismatches}\nThe easiest method is to set these DeepSpeed config values to 'auto'."      )


a       :      List[str]  	=			None





def 				lowercase (					__magic_name__							):



					'''simple docstring'''







					global _hf_deepspeed_config_weak_ref
					# will go away automatically when HfDeepSpeedConfig is destroyed (when TrainingArguments is destroyed)
					UpperCAmelCase		:							Dict        =       weakref.ref(snake_case__							)





def 				lowercase (					):



					'''simple docstring'''







					global _hf_deepspeed_config_weak_ref
					UpperCAmelCase		:							Dict        =       None





def 				lowercase (					):



					'''simple docstring'''







					if _hf_deepspeed_config_weak_ref is not None and _hf_deepspeed_config_weak_ref() is not None:
										return _hf_deepspeed_config_weak_ref().is_zeroa()
					else:
										return False





def 				lowercase (					):



					'''simple docstring'''







					if _hf_deepspeed_config_weak_ref is not None and _hf_deepspeed_config_weak_ref() is not None:
										return _hf_deepspeed_config_weak_ref().config
					else:
										return None





def 				lowercase (					__magic_name__			,   __magic_name__			,   __magic_name__			,   __magic_name__			,   __magic_name__							):



					'''simple docstring'''







					from accelerate.utils import DummyOptim, DummyScheduler

					UpperCAmelCase		:							Optional[int]        =       hf_deepspeed_config.config

					# Optimizer + Scheduler
					# Currently supported combos:
					# 1. DS scheduler + DS optimizer: Yes
					# 2. HF scheduler + HF optimizer: Yes
					# 3. DS scheduler + HF optimizer: Yes
					# 4. HF scheduler + DS optimizer: No
					#
					# Unless Offload is enabled in which case it's:
					# 1. DS scheduler + DS optimizer: Yes
					# 2. HF scheduler + HF optimizer: Mostly*
					# 3. DS scheduler + HF optimizer: Mostly*
					# 4. HF scheduler + DS optimizer: No
					#
					# Mostly*: All non-native DeepSpeed optimizers that have both CPU and GPU implementation should work (except LAMB)

					UpperCAmelCase		:							str        =       None
					if "optimizer" in config:
										if args.adafactor:
															raise ValueError(
															    "--adafactor was passed, but also found `optimizer` configured in the DeepSpeed config. "
															    "Only one optimizer can be configured."							)
										UpperCAmelCase		:							List[Any]        =       DummyOptim(params=snake_case__							)
					else:
										if hf_deepspeed_config.is_offload():
															logger.info(
															    "Detected ZeRO Offload and non-DeepSpeed optimizers: This combination should work as long as the"
															    " custom optimizer has both CPU and GPU implementation (except LAMB)"							)

										# ds supports Adam, OneBitAdam, and Lamb optimizers and can import other optimizers from torch.
										# But trainer uses AdamW by default.
										UpperCAmelCase		:							List[Any]        =       trainer.create_optimizer()
										# To use other optimizers requires voiding warranty with: `zero_allow_untested_optimizer`
										UpperCAmelCase		:							Union[str, Any]        =       True

					UpperCAmelCase		:							Optional[Any]        =       None
					if "scheduler" in config:
										UpperCAmelCase		:							Union[str, Any]        =       DummyScheduler(snake_case__							)
					else:
										if isinstance(snake_case__			,   snake_case__							):
															raise ValueError(
															    "Found `optimizer` configured in the DeepSpeed config, but no `scheduler`. "
															    "Please configure a scheduler in the DeepSpeed config."							)
										UpperCAmelCase		:							Union[str, Any]        =       trainer.create_scheduler(num_training_steps=snake_case__			,   optimizer=snake_case__							)

					return optimizer, lr_scheduler





def 				lowercase (					__magic_name__			,   __magic_name__			,   __magic_name__=False							):



					'''simple docstring'''







					from deepspeed.utils import logger as ds_logger

					UpperCAmelCase		:							Union[str, Any]        =       trainer.model
					UpperCAmelCase		:							Union[str, Any]        =       trainer.args

					UpperCAmelCase		:							Any        =       trainer.accelerator.state.deepspeed_plugin.hf_ds_config

					# resume config update - some bits like `model` and `num_training_steps` only become available during train
					hf_deepspeed_config.trainer_config_finalize(snake_case__			,   snake_case__			,   snake_case__							)

					# set the Deepspeed log level consistent with the Trainer
					ds_logger.setLevel(args.get_process_log_level()							)

					if inference:
										# only Z3 makes sense for the inference
										if not hf_deepspeed_config.is_zeroa():
															raise ValueError("ZeRO inference only makes sense with ZeRO Stage 3 - please adjust your config"							)

										# in case the training config is re-used for inference
										hf_deepspeed_config.del_config_sub_tree("optimizer"							)
										hf_deepspeed_config.del_config_sub_tree("lr_scheduler"							)
										UpperCAmelCase ,			UpperCAmelCase		:							Union[str, Any]        =       None, None
										UpperCAmelCase		:							Any        =       None
					else:
										UpperCAmelCase		:							str        =       None  # important for when deepspeed_init is used as re-init
										UpperCAmelCase		:							Dict        =       list(filter(lambda __magic_name__							: p.requires_grad			,   model.parameters()							)							)
										UpperCAmelCase ,			UpperCAmelCase		:							str        =       deepspeed_optim_sched(
										    snake_case__			,   snake_case__			,   snake_case__			,   snake_case__			,   snake_case__							)

					# keep for quick debug:
					# from pprint import pprint; pprint(config)

					return optimizer, lr_scheduler





def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







					import glob

					UpperCAmelCase		:							int        =       sorted(glob.glob(F"{checkpoint_path}/global_step*"							)							)

					if len(snake_case__							) > 0:
										logger.info(F"Attempting to resume from {checkpoint_path}"							)
										# this magically updates self.optimizer and self.lr_scheduler
										UpperCAmelCase ,			UpperCAmelCase		:							int        =       deepspeed_engine.load_checkpoint(
										    snake_case__			,   load_optimizer_states=snake_case__			,   load_lr_scheduler_states=snake_case__							)
										if load_path is None:
															raise ValueError(F"[deepspeed] failed to resume from checkpoint {checkpoint_path}"							)
					else:
										raise ValueError(F"Can't find a valid checkpoint at {checkpoint_path}"							)



'''simple docstring'''

from __future__ import annotations







class   UpperCamelCase__   :


		"""simple docstring"""

		def __init__(			self   ,      snake_case      ):


							'''simple docstring'''

							UpperCAmelCase		:							str        =       data
							UpperCAmelCase		:							Dict        =       None







class   UpperCamelCase__   :


		"""simple docstring"""

		def __init__(			self      ):


							'''simple docstring'''

							UpperCAmelCase		:							str        =       None







		def 				A_	(			self   ,      snake_case      ):


							'''simple docstring'''

							UpperCAmelCase		:							int        =       Node(snake_case      )
							UpperCAmelCase		:							Optional[int]        =       self.head
							UpperCAmelCase		:							Union[str, Any]        =       new_node
							return self.head.data







		def 				A_	(			self      ):


							'''simple docstring'''

							UpperCAmelCase		:							Dict        =       self.head
							UpperCAmelCase		:							str        =       self.head
							if self.head:
												while fast_pointer and fast_pointer.next:
																	UpperCAmelCase		:							List[str]        =       fast_pointer.next.next
																	UpperCAmelCase		:							Any        =       slow_pointer.next
												return slow_pointer.data
							else:
												print("No element found."      )
												return None


if __name__ == "__main__":
				a       :      List[str]  	=			LinkedList()
				for _ in range(int(input().strip())):
								a       :      str  	=			int(input().strip())
								link.push(data)
				print(link.middle_element())
