



'''simple docstring'''
from __future__ import annotations

_UpperCamelCase											=			[2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]



class _A  :





		def __init__(     self ,       __UpperCAmelCase				)       ->     None:

					'''simple docstring'''
					__UpperCAmelCase   :      Optional[Any]										=     -1
					__UpperCAmelCase   :      int										=     -1
					__UpperCAmelCase   :      Any										=     [-1] * length
					__UpperCAmelCase   :      Union[str, Any]										=     None
					__UpperCAmelCase   :      Optional[Any]										=     None





		def __repr__(     self				)       ->     str:

					'''simple docstring'''
					return f'Node(min_value={self.minn} max_value={self.maxx})'


def   lowercase_	(   lowerCAmelCase__	:  list[int] ):

			"""simple docstring"""





			__UpperCAmelCase   :      Optional[int]										=     Node(len(__lowerCamelCase ) )
			__UpperCAmelCase				,  __UpperCAmelCase   :      Optional[int]										=     min(__lowerCamelCase ), max(__lowerCamelCase )
			# Leaf node case where the node contains only one unique value
			if root.minn == root.maxx:
						return root
			__UpperCAmelCase   :      Optional[int]										=     (root.minn + root.maxx) // 2

			__UpperCAmelCase   :      Any										=     []
			__UpperCAmelCase   :      Any										=     []

			for index, num in enumerate(__lowerCamelCase ):
						if num <= pivot:
									left_arr.append(__lowerCamelCase )
						else:
									right_arr.append(__lowerCamelCase )
						__UpperCAmelCase   :      Any										=     len(__lowerCamelCase )
			__UpperCAmelCase   :      int										=     build_tree(__lowerCamelCase )
			__UpperCAmelCase   :      Optional[int]										=     build_tree(__lowerCamelCase )
			return root


def   lowercase_	(   lowerCAmelCase__	:  Node | None			,							lowerCAmelCase__	:  int			,							lowerCAmelCase__	:  int ):

			"""simple docstring"""





			if index < 0 or node is None:
						return 0
			# Leaf node cases
			if node.minn == node.maxx:
						return index + 1 if node.minn == num else 0
			__UpperCAmelCase   :      Dict										=     (node.minn + node.maxx) // 2
			if num <= pivot:
						# go the left subtree and map index to the left subtree
						return rank_till_index(node.left			,							__lowerCamelCase			,							node.map_left[index] - 1 )
			else:
						# go to the right subtree and map index to the right subtree
						return rank_till_index(node.right			,							__lowerCamelCase			,							index - node.map_left[index] )


def   lowercase_	(   lowerCAmelCase__	:  Node | None			,							lowerCAmelCase__	:  int			,							lowerCAmelCase__	:  int			,							lowerCAmelCase__	:  int ):

			"""simple docstring"""





			if start > end:
						return 0
			__UpperCAmelCase   :      Tuple										=     rank_till_index(__lowerCamelCase			,							__lowerCamelCase			,							__lowerCamelCase )
			__UpperCAmelCase   :      Dict										=     rank_till_index(__lowerCamelCase			,							__lowerCamelCase			,							start - 1 )
			return rank_till_end - rank_before_start


def   lowercase_	(   lowerCAmelCase__	:  Node | None			,							lowerCAmelCase__	:  int			,							lowerCAmelCase__	:  int			,							lowerCAmelCase__	:  int ):

			"""simple docstring"""





			if index > (end - start) or start > end or node is None:
						return -1
			# Leaf node case
			if node.minn == node.maxx:
						return node.minn
			# Number of elements in the left subtree in interval [start, end]
			__UpperCAmelCase   :      Tuple										=     node.map_left[end] - (
			    node.map_left[start - 1] if start else 0
			)
			if num_elements_in_left_tree > index:
						return quantile(
						    node.left			,							__lowerCamelCase			,							(node.map_left[start - 1] if start else 0)			,							node.map_left[end] - 1			,							)
			else:
						return quantile(
						    node.right			,							index - num_elements_in_left_tree			,							start - (node.map_left[start - 1] if start else 0)			,							end - node.map_left[end]			,							)


def   lowercase_	(   lowerCAmelCase__	:  Node | None			,							lowerCAmelCase__	:  int			,							lowerCAmelCase__	:  int			,							lowerCAmelCase__	:  int			,							lowerCAmelCase__	:  int ):

			"""simple docstring"""





			if (
			    start > end
			    or node is None
			    or start_num > end_num
			    or node.minn > end_num
			    or node.maxx < start_num
			):
						return 0
			if start_num <= node.minn and node.maxx <= end_num:
						return end - start + 1
			__UpperCAmelCase   :      Tuple										=     range_counting(
			    node.left			,							(node.map_left[start - 1] if start else 0)			,							node.map_left[end] - 1			,							__lowerCamelCase			,							__lowerCamelCase			,							)
			__UpperCAmelCase   :      Optional[int]										=     range_counting(
			    node.right			,							start - (node.map_left[start - 1] if start else 0)			,							end - node.map_left[end]			,							__lowerCamelCase			,							__lowerCamelCase			,							)
			return left + right


if __name__ == "__main__":
					import doctest

					doctest.testmod()









'''simple docstring'''
from itertools import permutations


def   lowercase_	(   lowerCAmelCase__	:  int = 5 ):

			"""simple docstring"""





			if gon_side < 3 or gon_side > 5:
						raise ValueError("""gon_side must be in the range [3, 5]""" )

			# Since it's 16, we know 10 is on the outer ring
			# Put the big numbers at the end so that they are never the first number
			__UpperCAmelCase   :      int										=     list(range(gon_side + 1			,							0			,							-1 ) )
			__UpperCAmelCase   :      int										=     list(range(gon_side + 2			,							gon_side * 2 + 1 ) )

			for perm in permutations(small_numbers + big_numbers ):
						__UpperCAmelCase   :      Optional[int]										=     generate_gon_ring(lowerCAmelCase__			,							list(lowerCAmelCase__ ) )
						if is_magic_gon(lowerCAmelCase__ ):
									return int("""""".join(str(lowerCAmelCase__ ) for n in numbers ) )

			__UpperCAmelCase   :      Optional[int]										=     f'Magic {gon_side}-gon ring is impossible'
			raise ValueError(lowerCAmelCase__ )


def   lowercase_	(   lowerCAmelCase__	:  int			,							lowerCAmelCase__	:  list[int] ):

			"""simple docstring"""





			__UpperCAmelCase   :      Tuple										=     [0] * (gon_side * 3)
			__UpperCAmelCase   :      Optional[Any]										=     perm[0:3]
			perm.append(perm[1] )

			__UpperCAmelCase   :      Union[str, Any]										=     1 if gon_side < 5 else 2

			for i in range(1			,							len(lowerCAmelCase__ ) // 3 + magic_number ):
						__UpperCAmelCase   :      List[str]										=     perm[2 * i + 1]
						__UpperCAmelCase   :      Optional[int]										=     result[3 * i - 1]
						__UpperCAmelCase   :      Optional[int]										=     perm[2 * i + 2]

			return result


def   lowercase_	(   lowerCAmelCase__	:  list[int] ):

			"""simple docstring"""





			if len(lowerCAmelCase__ ) % 3 != 0:
						raise ValueError("""a gon ring should have a length that is a multiple of 3""" )

			if min(numbers[::3] ) != numbers[0]:
						return False

			__UpperCAmelCase   :      Optional[int]										=     sum(numbers[:3] )

			return all(sum(numbers[i : i + 3] ) == total for i in range(3			,							len(lowerCAmelCase__ )			,							3 ) )


if __name__ == "__main__":
					print(solution())




