






from __future__ import annotations

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


class        SCREAMING_SNAKE_CASE	:
     '''simple docstring'''


     def __init__( self				:		List[str]    ,       UpperCAmelCase_				:		int					):
       SCREAMING_SNAKE_CASE				:					Dict		  =			-1
       SCREAMING_SNAKE_CASE				:					int		  =			-1
       SCREAMING_SNAKE_CASE				:					List[str]		  =			[-1] * length
       SCREAMING_SNAKE_CASE				:					Union[str, Any]		  =			None
       SCREAMING_SNAKE_CASE				:					Union[str, Any]		  =			None






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





def      lowerCamelCase__	(   lowercase ):

  """simple docstring"""






  SCREAMING_SNAKE_CASE				:					Dict		  =			Node(len(__UpperCAmelCase ) )
  SCREAMING_SNAKE_CASE  ,     SCREAMING_SNAKE_CASE				:					Tuple		  =			min(__UpperCAmelCase ), max(__UpperCAmelCase )
  # Leaf node case where the node contains only one unique value
  if root.minn == root.maxx:
    return root
  SCREAMING_SNAKE_CASE				:					str		  =			(root.minn + root.maxx) // 2

  SCREAMING_SNAKE_CASE				:					Union[str, Any]		  =			[]
  SCREAMING_SNAKE_CASE				:					Tuple		  =			[]

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


def      lowerCamelCase__	(   lowercase  ,   lowercase  ,   lowercase ):

  """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
  SCREAMING_SNAKE_CASE				:					Optional[Any]		  =			(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  ,   __UpperCAmelCase  ,   node.map_left[index] - 1 )
  else:
    # go to the right subtree and map index to the right subtree
    return rank_till_index(node.right  ,   __UpperCAmelCase  ,   index - node.map_left[index] )


def      lowerCamelCase__	(   lowercase  ,   lowercase  ,   lowercase  ,   lowercase ):

  """simple docstring"""






  if start > end:
    return 0
  SCREAMING_SNAKE_CASE				:					int		  =			rank_till_index(__UpperCAmelCase  ,   __UpperCAmelCase  ,   __UpperCAmelCase )
  SCREAMING_SNAKE_CASE				:					Union[str, Any]		  =			rank_till_index(__UpperCAmelCase  ,   __UpperCAmelCase  ,   start - 1 )
  return rank_till_end - rank_before_start


def      lowerCamelCase__	(   lowercase  ,   lowercase  ,   lowercase  ,   lowercase ):

  """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]
  SCREAMING_SNAKE_CASE				:					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  ,   __UpperCAmelCase  ,   (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      lowerCamelCase__	(   lowercase  ,   lowercase  ,   lowercase  ,   lowercase  ,   lowercase ):

  """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
  SCREAMING_SNAKE_CASE				:					Dict		  =			range_counting(
      node.left  ,   (node.map_left[start - 1] if start else 0)  ,   node.map_left[end] - 1  ,   __UpperCAmelCase  ,   __UpperCAmelCase  ,   )
  SCREAMING_SNAKE_CASE				:					Union[str, Any]		  =			range_counting(
      node.right  ,   start - (node.map_left[start - 1] if start else 0)  ,   end - node.map_left[end]  ,   __UpperCAmelCase  ,   __UpperCAmelCase  ,   )
  return left + right


if __name__ == "__main__":
   import doctest

   doctest.testmod()











def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round((float(__UpperCAmelCase	) * 9 / 5) + 32							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round(float(__UpperCAmelCase	) + 273.15							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round((float(__UpperCAmelCase	) * 9 / 5) + 491.67							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round((float(__UpperCAmelCase	) - 32) * 5 / 9							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round(((float(__UpperCAmelCase	) - 32) * 5 / 9) + 273.15							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round(float(__UpperCAmelCase	) + 459.67							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round(float(__UpperCAmelCase	) - 273.15							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round(((float(__UpperCAmelCase	) - 273.15) * 9 / 5) + 32							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round((float(__UpperCAmelCase	) * 9 / 5)							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round((float(__UpperCAmelCase	) - 491.67) * 5 / 9							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round(float(__UpperCAmelCase	) - 459.67							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round((float(__UpperCAmelCase	) * 5 / 9)							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round((float(__UpperCAmelCase	) * 1.25 + 273.15)							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round((float(__UpperCAmelCase	) * 2.25 + 32)							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round((float(__UpperCAmelCase	) * 1.25)							,					__UpperCAmelCase	)







def 				A			(		__UpperCAmelCase							,					__UpperCAmelCase = 2	)       ->       float:



						'''simple docstring'''






						return round((float(__UpperCAmelCase	) * 2.25 + 32 + 459.67)							,					__UpperCAmelCase	)


if __name__ == "__main__":
							import doctest

							doctest.testmod()





