
from __future__ import annotations

__SCREAMING_SNAKE_CASE			:   Optional[Any]         =     [2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]


class 		__magic_name__   :





		def __init__(							self    :	List[Any]						,  lowerCamelCase__    :	int				):
							lowerCAmelCase		:					int  	=     -1
							lowerCAmelCase		:					int  	=     -1
							lowerCAmelCase		:					list[int]  	=     [-1] * length
							lowerCAmelCase		:					Node | None  	=     None
							lowerCAmelCase		:					Node | None  	=     None





		def __repr__(							self    :	Any				):
							return f'''Node(min_value={self.minn} max_value={self.maxx})'''



def     UpperCAmelCase__							(       __magic_name__						:     list[int]  ):


					'''simple docstring'''

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

					lowerCAmelCase		:					list[int]  	=     []
					lowerCAmelCase		:					list[int]  	=     []

					for index, num in enumerate(__magic_name__  ):
										if num <= pivot:
															left_arr.append(__magic_name__  )
										else:
															right_arr.append(__magic_name__  )
										lowerCAmelCase		:					Optional[Any]  	=     len(__magic_name__  )
					lowerCAmelCase		:					int  	=     build_tree(__magic_name__  )
					lowerCAmelCase		:					Tuple  	=     build_tree(__magic_name__  )
					return root
def     UpperCAmelCase__							(       __magic_name__						:     Node | None							,  __magic_name__						:     int							,  __magic_name__						:     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
					lowerCAmelCase		:					List[str]  	=     (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							,  __magic_name__							,  node.map_left[index] - 1  )
					else:
										# go to the right subtree and map index to the right subtree
										return rank_till_index(node.right							,  __magic_name__							,  index - node.map_left[index]  )
def     UpperCAmelCase__							(       __magic_name__						:     Node | None							,  __magic_name__						:     int							,  __magic_name__						:     int							,  __magic_name__						:     int  ):


					'''simple docstring'''

					if start > end:
										return 0
					lowerCAmelCase		:					str  	=     rank_till_index(__magic_name__							,  __magic_name__							,  __magic_name__  )
					lowerCAmelCase		:					Optional[int]  	=     rank_till_index(__magic_name__							,  __magic_name__							,  start - 1  )
					return rank_till_end - rank_before_start
def     UpperCAmelCase__							(       __magic_name__						:     Node | None							,  __magic_name__						:     int							,  __magic_name__						:     int							,  __magic_name__						:     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]
					lowerCAmelCase		:					List[str]  	=     node.map_left[end] - (
					    node.map_left[start - 1] if start else 0
					)
					if num_elements_in_left_tree > index:
										return quantile(
										    node.left							,  __magic_name__							,  (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     UpperCAmelCase__							(       __magic_name__						:     Node | None							,  __magic_name__						:     int							,  __magic_name__						:     int							,  __magic_name__						:     int							,  __magic_name__						:     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
					lowerCAmelCase		:					Dict  	=     range_counting(
					    node.left							,  (node.map_left[start - 1] if start else 0)							,  node.map_left[end] - 1							,  __magic_name__							,  __magic_name__							,  )
					lowerCAmelCase		:					List[str]  	=     range_counting(
					    node.right							,  start - (node.map_left[start - 1] if start else 0)							,  end - node.map_left[end]							,  __magic_name__							,  __magic_name__							,  )
					return left + right


if __name__ == "__main__":
		import doctest

		doctest.testmod()


def     UpperCAmelCase__							(       __magic_name__						:     Tuple							,  __magic_name__						:     int							,  __magic_name__						:     Dict							,  __magic_name__						:     str  ):


					'''simple docstring'''

					if start == end:
										return start if lst[start] > item else start + 1
					if start > end:
										return start

					lowerCAmelCase		:					Optional[Any]  	=     (start + end) // 2
					if lst[mid] < item:
										return binary_search(__magic_name__							,  __magic_name__							,  mid + 1							,  __magic_name__  )
					elif lst[mid] > item:
										return binary_search(__magic_name__							,  __magic_name__							,  __magic_name__							,  mid - 1  )
					else:
										return mid
def     UpperCAmelCase__							(       __magic_name__						:     List[Any]  ):


					'''simple docstring'''

					lowerCAmelCase		:					Union[str, Any]  	=     len(__magic_name__  )

					for index in range(1							,  __magic_name__  ):
										lowerCAmelCase		:					Optional[int]  	=     lst[index]
										lowerCAmelCase		:					Dict  	=     binary_search(__magic_name__							,  __magic_name__							,  0							,  index - 1  )
										lowerCAmelCase		:					Union[str, Any]  	=     lst[:pos] + [value] + lst[pos:index] + lst[index + 1 :]

					return lst
def     UpperCAmelCase__							(       __magic_name__						:     Optional[int]							,  __magic_name__						:     List[str]  ):


					'''simple docstring'''

					if not left:
										return right

					if not right:
										return left

					if left[0] < right[0]:
										return [left[0], *merge(left[1:]							,  __magic_name__  )]

					return [right[0], *merge(__magic_name__							,  right[1:]  )]
def     UpperCAmelCase__							(       __magic_name__						:     str  ):


					'''simple docstring'''

					lowerCAmelCase		:					str  	=     len(__magic_name__  )
					lowerCAmelCase	,							lowerCAmelCase		:					Union[str, Any]  	=     [], []
					lowerCAmelCase		:					Union[str, Any]  	=     [lst[0]]
					lowerCAmelCase		:					Optional[Any]  	=     []
					lowerCAmelCase		:					List[Any]  	=     1
					while i < length:
										if lst[i] < lst[i - 1]:
															runs.append(__magic_name__  )
															lowerCAmelCase		:					Any  	=     [lst[i]]
										else:
															new_run.append(lst[i]  )
										i += 1
					runs.append(__magic_name__  )

					for run in runs:
										sorted_runs.append(insertion_sort(__magic_name__  )  )
					for run in sorted_runs:
										lowerCAmelCase		:					int  	=     merge(__magic_name__							,  __magic_name__  )

					return sorted_array
def     UpperCAmelCase__							(       ):


					'''simple docstring'''

					lowerCAmelCase		:					Tuple  	=     [5, 9, 10, 3, -4, 5, 1_78, 92, 46, -18, 0, 7]
					lowerCAmelCase		:					Optional[Any]  	=     tim_sort(__magic_name__  )
					print(__magic_name__  )


if __name__ == "__main__":
		main()
