




"""simple docstring"""






import re
from typing import Callable, List, Optional, Union

import tensorflow as tf


try:
			from tensorflow.keras.optimizers.legacy import Adam
except ImportError:
			from tensorflow.keras.optimizers import Adam






class lowerCAmelCase__	(     tf.keras.optimizers.schedules.LearningRateSchedule						):






			'''simple docstring'''



			def __init__(  self  ,      lowercase  ,      lowercase  ,      lowercase  ,      lowercase = 1.0  ,      lowercase = None  ,      ):
							super().__init__()
							_lowerCamelCase     :			str    =    initial_learning_rate
							_lowerCamelCase     :			Any    =    warmup_steps
							_lowerCamelCase     :			List[Any]    =    power
							_lowerCamelCase     :			List[Any]    =    decay_schedule_fn
							_lowerCamelCase     :			int    =    name
			def __call__(  self  ,      lowercase  ):
							with tf.name_scope(self.name or 'WarmUp'  ) as name:
											# Implements polynomial warmup. i.e., if global_step < warmup_steps, the
											# learning rate will be `global_step/num_warmup_steps * init_lr`.
											_lowerCamelCase     :			Optional[int]    =    tf.cast(lowercase  ,      tf.floataa  )
											_lowerCamelCase     :			Optional[Any]    =    tf.cast(self.warmup_steps  ,      tf.floataa  )
											_lowerCamelCase     :			Any    =    global_step_float / warmup_steps_float
											_lowerCamelCase     :			Dict    =    self.initial_learning_rate * tf.math.pow(lowercase  ,      self.power  )
											return tf.cond(
											    global_step_float < warmup_steps_float  ,      lambda: warmup_learning_rate  ,      lambda: self.decay_schedule_fn(step - self.warmup_steps  )  ,      name=lowercase  ,      )






			def 					A_    (  self  ):
							return {
							    "initial_learning_rate": self.initial_learning_rate,
							    "decay_schedule_fn": self.decay_schedule_fn,
							    "warmup_steps": self.warmup_steps,
							    "power": self.power,
							    "name": self.name,
							}







def      _snake_case			(				lowercase__							,    lowercase__							,    lowercase__							,    lowercase__ = 0.0							,    lowercase__ = 0.9							,    lowercase__ = 0.9_9_9							,    lowercase__ = 1E-8							,    lowercase__ = None							,    lowercase__ = None							,    lowercase__ = 0.0							,    lowercase__ = 1.0							,    lowercase__ = None							,    ):
				_lowerCamelCase     :			Any    =    tf.keras.optimizers.schedules.PolynomialDecay(
				    initial_learning_rate=lowercase__							,    decay_steps=num_train_steps - num_warmup_steps							,    end_learning_rate=init_lr * min_lr_ratio							,    power=lowercase__							,    )
				if num_warmup_steps:
								_lowerCamelCase     :			Optional[int]    =    WarmUp(
								    initial_learning_rate=lowercase__							,    decay_schedule_fn=lowercase__							,    warmup_steps=lowercase__							,    )
				if weight_decay_rate > 0.0:
								_lowerCamelCase     :			List[Any]    =    AdamWeightDecay(
								    learning_rate=lowercase__							,    weight_decay_rate=lowercase__							,    beta_a=lowercase__							,    beta_a=lowercase__							,    epsilon=lowercase__							,    clipnorm=lowercase__							,    global_clipnorm=lowercase__							,    exclude_from_weight_decay=['LayerNorm', 'layer_norm', 'bias']							,    include_in_weight_decay=lowercase__							,    )
				else:
								_lowerCamelCase     :			Any    =    tf.keras.optimizers.Adam(
								    learning_rate=lowercase__							,    beta_a=lowercase__							,    beta_a=lowercase__							,    epsilon=lowercase__							,    clipnorm=lowercase__							,    global_clipnorm=lowercase__							,    )
				# We return the optimizer and the LR scheduler in order to better track the
				# evolution of the LR independently of the optimizer.
				return optimizer, lr_schedule






class lowerCAmelCase__	(     lowercase						):






			'''simple docstring'''



			def __init__(  self  ,      lowercase = 0.0_01  ,      lowercase = 0.9  ,      lowercase = 0.9_99  ,      lowercase = 1E-7  ,      lowercase = False  ,      lowercase = 0.0  ,      lowercase = None  ,      lowercase = None  ,      lowercase = "AdamWeightDecay"  ,      **lowercase  ,      ):
							super().__init__(lowercase  ,      lowercase  ,      lowercase  ,      lowercase  ,      lowercase  ,      lowercase  ,      **lowercase  )
							_lowerCamelCase     :			str    =    weight_decay_rate
							_lowerCamelCase     :			List[str]    =    include_in_weight_decay
							_lowerCamelCase     :			List[str]    =    exclude_from_weight_decay
			@classmethod
			def 					A_    (  cls  ,      lowercase  ):
							_lowerCamelCase     :			List[Any]    =    {'WarmUp': WarmUp}
							return super(lowercase  ,      cls  ).from_config(lowercase  ,      custom_objects=lowercase  )
			def 					A_    (  self  ,      lowercase  ,      lowercase  ,      lowercase  ):
							super(lowercase  ,      self  )._prepare_local(lowercase  ,      lowercase  ,      lowercase  )
							_lowerCamelCase     :			Any    =    tf.constant(
							    self.weight_decay_rate  ,      name='adam_weight_decay_rate'  )
			def 					A_    (  self  ,      lowercase  ,      lowercase  ,      lowercase  ):
							_lowerCamelCase     :			List[Any]    =    self._do_use_weight_decay(var.name  )
							if do_decay:
											return var.assign_sub(
											    learning_rate * var * apply_state[(var.device, var.dtype.base_dtype)]['weight_decay_rate']  ,      use_locking=self._use_locking  ,      )
							return tf.no_op()
			def 					A_    (  self  ,      lowercase  ,      lowercase=None  ,      **lowercase  ):
							_lowerCamelCase, _lowerCamelCase     :			List[str]    =    list(zip(*lowercase  )  )
							return super(lowercase  ,      self  ).apply_gradients(zip(lowercase  ,      lowercase  )  ,      name=lowercase  ,      **lowercase  )
			def 					A_    (  self  ,      lowercase  ,      lowercase  ,      lowercase  ):
							if apply_state is None:
											return self._decayed_lr_t[var_dtype], {}

							_lowerCamelCase     :			Any    =    apply_state or {}
							_lowerCamelCase     :			List[Any]    =    apply_state.get((var_device, var_dtype)  )
							if coefficients is None:
											_lowerCamelCase     :			List[str]    =    self._fallback_apply_state(lowercase  ,      lowercase  )
											_lowerCamelCase     :			Tuple    =    coefficients

							return coefficients["lr_t"], {"apply_state": apply_state}
			def 					A_    (  self  ,      lowercase  ,      lowercase  ,      lowercase=None  ):
							_lowerCamelCase, _lowerCamelCase     :			List[Any]    =    self._get_lr(var.device  ,      var.dtype.base_dtype  ,      lowercase  )
							_lowerCamelCase     :			Dict    =    self._decay_weights_op(lowercase  ,      lowercase  ,      lowercase  )
							with tf.control_dependencies([decay]  ):
											return super(lowercase  ,      self  )._resource_apply_dense(lowercase  ,      lowercase  ,      **lowercase  )
			def 					A_    (  self  ,      lowercase  ,      lowercase  ,      lowercase  ,      lowercase=None  ):
							_lowerCamelCase, _lowerCamelCase     :			Optional[Any]    =    self._get_lr(var.device  ,      var.dtype.base_dtype  ,      lowercase  )
							_lowerCamelCase     :			int    =    self._decay_weights_op(lowercase  ,      lowercase  ,      lowercase  )
							with tf.control_dependencies([decay]  ):
											return super(lowercase  ,      self  )._resource_apply_sparse(lowercase  ,      lowercase  ,      lowercase  ,      **lowercase  )
			def 					A_    (  self  ):
							_lowerCamelCase     :			Optional[Any]    =    super().get_config()
							config.update({'weight_decay_rate': self.weight_decay_rate}  )
							return config






			def 					A_    (  self  ,      lowercase  ):
							if self.weight_decay_rate == 0:
											return False

							if self._include_in_weight_decay:
											for r in self._include_in_weight_decay:
															if re.search(lowercase  ,      lowercase  ) is not None:
																			return True

							if self._exclude_from_weight_decay:
											for r in self._exclude_from_weight_decay:
															if re.search(lowercase  ,      lowercase  ) is not None:
																			return False
							return True






class lowerCAmelCase__	(     lowercase						):






			'''simple docstring'''



			def __init__(  self  ):
							_lowerCamelCase     :			Optional[Any]    =    []
							_lowerCamelCase     :			Dict    =    None
			@property
			def 					A_    (  self  ):
							if self._accum_steps is None:
											_lowerCamelCase     :			str    =    tf.Variable(
											    tf.constant(0  ,      dtype=tf.intaa  )  ,      trainable=lowercase  ,      synchronization=tf.VariableSynchronization.ON_READ  ,      aggregation=tf.VariableAggregation.ONLY_FIRST_REPLICA  ,      )

							return self._accum_steps.value()
			@property
			def 					A_    (  self  ):
							if not self._gradients:
											raise ValueError('The accumulator should be called first to initialize the gradients'  )
							return [gradient.value() if gradient is not None else gradient for gradient in self._gradients]
			def __call__(  self  ,      lowercase  ):
							if not self._gradients:
											_lowerCamelCase     :			Any    =    self.step  # Create the step variable.
											self._gradients.extend(
											    [
											        tf.Variable(
											            tf.zeros_like(lowercase  )  ,      trainable=lowercase  ,      synchronization=tf.VariableSynchronization.ON_READ  ,      aggregation=tf.VariableAggregation.ONLY_FIRST_REPLICA  ,      )
											        if gradient is not None
											        else gradient
											        for gradient in gradients
											    ]  )
							if len(lowercase  ) != len(self._gradients  ):
											raise ValueError(F'''Expected {len(self._gradients  )} gradients, but got {len(lowercase  )}'''  )

							for accum_gradient, gradient in zip(self._gradients  ,      lowercase  ):
											if accum_gradient is not None and gradient is not None:
															accum_gradient.assign_add(lowercase  )

							self._accum_steps.assign_add(1  )






			def 					A_    (  self  ):
							if not self._gradients:
											return
							self._accum_steps.assign(0  )
							for gradient in self._gradients:
											if gradient is not None:
															gradient.assign(tf.zeros_like(lowercase  )  )





"""simple docstring"""






def      _snake_case			(				lowercase__		):
				stooge(lowercase__							,    0							,    len(lowercase__		) - 1		)
				return arr







def      _snake_case			(				lowercase__							,    lowercase__							,    lowercase__		):
				if i >= h:
								return

				# If first element is smaller than the last then swap them
				if arr[i] > arr[h]:
								_lowerCamelCase, _lowerCamelCase     :			Optional[Any]    =    arr[h], arr[i]

				# If there are more than 2 elements in the array
				if h - i + 1 > 2:
								_lowerCamelCase     :			Union[str, Any]    =    (int)((h - i + 1) / 3		)

								# Recursively sort first 2/3 elements
								stooge(lowercase__							,    lowercase__							,    (h - t)		)

								# Recursively sort last 2/3 elements
								stooge(lowercase__							,    i + t							,    (lowercase__)		)

								# Recursively sort first 2/3 elements
								stooge(lowercase__							,    lowercase__							,    (h - t)		)


if __name__ == "__main__":
			lowercase__     						=						input("""Enter numbers separated by a comma:\n""").strip()
			lowercase__     						=						[int(item) for item in user_input.split(""",""")]
			print(stooge_sort(unsorted))