

from __future__ import annotations

from collections import namedtuple
from dataclasses import dataclass

@dataclass
class __UpperCamelCase     :






					'''simple docstring'''



					__magic_name__        =   42
					__magic_name__        =   None
					__magic_name__        =   None
_lowerCAmelCase  :      Any			 =namedtuple("""CoinsDistribResult""", """moves excess""")



def 			_A	(      SCREAMING_SNAKE_CASE      ):

	if root is None:
		return 0

	# Validation
	def count_nodes(SCREAMING_SNAKE_CASE      ) -> int:
		if node is None:
			return 0

		return count_nodes(node.left      ) + count_nodes(node.right      ) + 1

	def count_coins(SCREAMING_SNAKE_CASE      ) -> int:
		if node is None:
			return 0

		return count_coins(node.left      ) + count_coins(node.right      ) + node.data

	if count_nodes(SCREAMING_SNAKE_CASE      ) != count_coins(SCREAMING_SNAKE_CASE      ):
		raise ValueError("The nodes number should be same as the number of coins"      )

	# Main calculation
	def get_distrib(SCREAMING_SNAKE_CASE      ) -> CoinsDistribResult:

		if node is None:
			return CoinsDistribResult(0	,1      )

		UpperCAmelCase__							,						UpperCAmelCase__:	List[str]									= get_distrib(node.left      )
		UpperCAmelCase__							,						UpperCAmelCase__:	Optional[int]									= get_distrib(node.right      )

		UpperCAmelCase__:	Tuple									= 1 - left_distrib_excess
		UpperCAmelCase__:	Any									= 1 - right_distrib_excess

		UpperCAmelCase__:	Optional[Any]									= (
		    left_distrib_moves
		    + right_distrib_moves
		    + abs(SCREAMING_SNAKE_CASE      )
		    + abs(SCREAMING_SNAKE_CASE      )
		)
		UpperCAmelCase__:	str									= node.data - coins_to_left - coins_to_right

		return CoinsDistribResult(SCREAMING_SNAKE_CASE	,SCREAMING_SNAKE_CASE      )

	return get_distrib(SCREAMING_SNAKE_CASE      )[0]


if __name__ == "__main__":
					import doctest

					doctest.testmod()


def 			_A	(      SCREAMING_SNAKE_CASE      ):
	stooge(SCREAMING_SNAKE_CASE	,0	,len(SCREAMING_SNAKE_CASE      ) - 1      )
	return arr



def 			_A	(      SCREAMING_SNAKE_CASE	,SCREAMING_SNAKE_CASE	,SCREAMING_SNAKE_CASE      ):
	if i >= h:
		return

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

	# If there are more than 2 elements in the array
	if h - i + 1 > 2:
		UpperCAmelCase__:	str									= (int)((h - i + 1) / 3      )

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

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

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


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