from __future__ import annotations

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





class 					__snake_case    :




					def __init__(  self       ,			__UpperCamelCase						)	->    None:



									'''simple docstring'''







									snake_case__   :      int   				= -1
									snake_case__   :      int   				= -1
									snake_case__   :      list[int]   				= [-1] * length
									snake_case__   :      Node | None   				= None
									snake_case__   :      Node | None   				= None




					def __repr__(  self						)	->    str:



									'''simple docstring'''







									return F"""Node(min_value={self.minn} max_value={self.maxx})"""




def 					UpperCamelCase__		(							A__       )  ->   Node | None:
				snake_case__   :      List[Any]   				= Node(len(A__       )       )
				snake_case__				,    snake_case__   :      Union[str, Any]   				= min(A__       ), max(A__       )
				# Leaf node case where the node contains only one unique value
				if root.minn == root.maxx:
								return root
				snake_case__   :      Optional[int]   				= (root.minn + root.maxx) // 2

				snake_case__   :      list[int]   				= []
				snake_case__   :      list[int]   				= []

				for index, num in enumerate(A__       ):
								if num <= pivot:
												left_arr.append(A__       )
								else:
												right_arr.append(A__       )
								snake_case__   :      Union[str, Any]   				= len(A__       )
				snake_case__   :      Any   				= build_tree(A__       )
				snake_case__   :      List[Any]   				= build_tree(A__       )
				return root
def 					UpperCamelCase__		(							A__     ,					A__     ,					A__       )  ->   int:
				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
				snake_case__   :      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     ,					A__     ,					node.map_left[index] - 1       )
				else:
								# go to the right subtree and map index to the right subtree
								return rank_till_index(node.right     ,					A__     ,					index - node.map_left[index]       )
def 					UpperCamelCase__		(							A__     ,					A__     ,					A__     ,					A__       )  ->   int:
				if start > end:
								return 0
				snake_case__   :      Any   				= rank_till_index(A__     ,					A__     ,					A__       )
				snake_case__   :      Tuple   				= rank_till_index(A__     ,					A__     ,					start - 1       )
				return rank_till_end - rank_before_start
def 					UpperCamelCase__		(							A__     ,					A__     ,					A__     ,					A__       )  ->   int:
				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]
				snake_case__   :      List[Any]   				= node.map_left[end] - (
				    node.map_left[start - 1] if start else 0
				)
				if num_elements_in_left_tree > index:
								return quantile(
								    node.left     ,					A__     ,					(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__		(							A__     ,					A__     ,					A__     ,					A__     ,					A__       )  ->   int:
				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
				snake_case__   :      Dict   				= range_counting(
				    node.left     ,					(node.map_left[start - 1] if start else 0)     ,					node.map_left[end] - 1     ,					A__     ,					A__     ,					)
				snake_case__   :      Tuple   				= range_counting(
				    node.right     ,					start - (node.map_left[start - 1] if start else 0)     ,					end - node.map_left[end]     ,					A__     ,					A__     ,					)
				return left + right


if __name__ == "__main__":
				import doctest

				doctest.testmod()



def 					UpperCamelCase__		(							A__     ,					A__       )  ->   Any:
				if len(str(A__       )       ) == 1 or len(str(A__       )       ) == 1:
								return a * b

				snake_case__   :      Union[str, Any]   				= max(len(str(A__       )       )     ,					len(str(A__       )       )       )
				snake_case__   :      str   				= ma // 2

				snake_case__				,    snake_case__   :      Tuple   				= divmod(A__     ,					10**ma       )
				snake_case__				,    snake_case__   :      str   				= divmod(A__     ,					10**ma       )

				snake_case__   :      Optional[int]   				= karatsuba(A__     ,					A__       )
				snake_case__   :      List[Any]   				= karatsuba((aa + aa)     ,					(ba + ba)       )
				snake_case__   :      Tuple   				= karatsuba(A__     ,					A__       )

				return (z * 10 ** (2 * ma)) + ((y - z - x) * 10 ** (ma)) + (x)
def 					UpperCamelCase__		(							)  ->   Optional[int]:
				print(karatsuba(1_5463     ,					2_3489       )       )


if __name__ == "__main__":
				main()


