'''simple docstring'''


from __future__ import annotations

from collections import deque
from enum import Enum
from math import atana, degrees
from sys import maxsize






class 	__SCREAMING_SNAKE_CASE		(			lowerCamelCase_			):







  '''simple docstring'''






  lowerCamelCase_						:Tuple		       =						1
  lowerCamelCase_						:List[Any]		       =						2
  lowerCamelCase_						:Any		       =						3


  def __repr__(					self		):




       '''simple docstring'''

       return F'''{self.__class__.__name__}.{self.name}'''







def    _lowerCamelCase       ( lowerCamelCase_   :				tuple[int, int]      ,	lowerCamelCase_   :				int      ,	lowerCamelCase_   :				int  ):



     """simple docstring"""





     UpperCAmelCase_  ,     UpperCAmelCase_				:  Tuple  = point
     return degrees(atana(y - miny      ,	x - minx  )  )


def    _lowerCamelCase       ( lowerCamelCase_   :				tuple[int, int]      ,	lowerCamelCase_   :				tuple[int, int]      ,	lowerCamelCase_   :				tuple[int, int]  ):



     """simple docstring"""





     UpperCAmelCase_  ,     UpperCAmelCase_				:  Union[str, Any]  = starting
     UpperCAmelCase_  ,     UpperCAmelCase_				:  Optional[Any]  = via
     UpperCAmelCase_  ,     UpperCAmelCase_				:  List[Any]  = target
     UpperCAmelCase_				:  Any  = degrees(atana(ya - ya      ,	xa - xa  )  )
     via_angle %= 360
     UpperCAmelCase_				:  Union[str, Any]  = degrees(atana(ya - ya      ,	xa - xa  )  )
     target_angle %= 360
     # t-
     #  \ \
     #   \ v
     #    \|
     #     s
     # via_angle is always lower than target_angle, if direction is left.
     # If they are same, it means they are on a same line of convex hull.
     if target_angle > via_angle:
          return Direction.left
     elif target_angle == via_angle:
          return Direction.straight
     else:
          return Direction.right





def    _lowerCamelCase       ( lowerCamelCase_   :				list[tuple[int, int]]  ):



     """simple docstring"""





     if len(lowerCamelCase_  ) <= 2:
          # There is no convex hull
          raise ValueError('graham_scan: argument must contain more than 3 points.'  )
     if len(lowerCamelCase_  ) == 3:
          return points
     # find the lowest and the most left point
     UpperCAmelCase_				:  Union[str, Any]  = 0
     UpperCAmelCase_  ,     UpperCAmelCase_				:  Any  = maxsize, maxsize
     for i, point in enumerate(lowerCamelCase_  ):
          UpperCAmelCase_				:  Optional[Any]  = point[0]
          UpperCAmelCase_				:  Dict  = point[1]
          if y < miny:
               UpperCAmelCase_				:  List[Any]  = y
               UpperCAmelCase_				:  Union[str, Any]  = x
               UpperCAmelCase_				:  Union[str, Any]  = i
          if y == miny and x < minx:
               UpperCAmelCase_				:  Dict  = x
               UpperCAmelCase_				:  Optional[Any]  = i

    # remove the lowest and the most left point from points for preparing for sort
     points.pop(lowerCamelCase_  )

     UpperCAmelCase_				:  List[str]  = sorted(lowerCamelCase_      ,	key=lambda lowerCamelCase_  : angle_comparer(lowerCamelCase_      ,	lowerCamelCase_      ,	lowerCamelCase_  )  )
     # This insert actually costs complexity,
     # and you should instead add (minx, miny) into stack later.
     # I'm using insert just for easy understanding.
     sorted_points.insert(0      ,	(minx, miny)  )

     UpperCAmelCase_				:  deque[tuple[int, int]]  = deque()
     stack.append(sorted_points[0]  )
     stack.append(sorted_points[1]  )
     stack.append(sorted_points[2]  )
     # In any ways, the first 3 points line are towards left.
     # Because we sort them the angle from minx, miny.
     UpperCAmelCase_				:  List[Any]  = Direction.left

     for i in range(3      ,	len(lowerCamelCase_  )  ):
          while True:
               UpperCAmelCase_				:  Union[str, Any]  = stack[-2]
               UpperCAmelCase_				:  Any  = stack[-1]
               UpperCAmelCase_				:  Optional[Any]  = sorted_points[i]
               UpperCAmelCase_				:  List[str]  = check_direction(lowerCamelCase_      ,	lowerCamelCase_      ,	lowerCamelCase_  )

               if next_direction == Direction.left:
                    UpperCAmelCase_				:  List[str]  = Direction.left
                    break
               if next_direction == Direction.straight:
                    if current_direction == Direction.left:
                         # We keep current_direction as left.
                         # Because if the straight line keeps as straight,
                         # we want to know if this straight line is towards left.
                         break
                    elif current_direction == Direction.right:
                         # If the straight line is towards right,
                         # every previous points on those straigh line is not convex hull.
                         stack.pop()
               if next_direction == Direction.right:
                    stack.pop()
          stack.append(sorted_points[i]  )
     return list(lowerCamelCase_  )







'''simple docstring'''


from __future__ import annotations

snake_case__	:     str      =    [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 ,						snake_case_		):




       '''simple docstring'''

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






  def __repr__(					self		):




       '''simple docstring'''

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







def    _lowerCamelCase       ( lowerCamelCase_   :				list[int]  ):



     """simple docstring"""





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

     UpperCAmelCase_				:  list[int]  = []
     UpperCAmelCase_				:  list[int]  = []

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


def    _lowerCamelCase       ( 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_				:  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      ,	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    _lowerCamelCase       ( lowerCamelCase_   :				Node | None      ,	lowerCamelCase_   :				int      ,	lowerCamelCase_   :				int      ,	lowerCamelCase_   :				int  ):



     """simple docstring"""





     if start > end:
          return 0
     UpperCAmelCase_				:  int  = rank_till_index(lowerCamelCase_      ,	lowerCamelCase_      ,	lowerCamelCase_  )
     UpperCAmelCase_				:  List[Any]  = rank_till_index(lowerCamelCase_      ,	lowerCamelCase_      ,	start - 1  )
     return rank_till_end - rank_before_start


def    _lowerCamelCase       ( 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    _lowerCamelCase       ( 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_				:  Any  = range_counting(
         node.left      ,	(node.map_left[start - 1] if start else 0)      ,	node.map_left[end] - 1      ,	lowerCamelCase_      ,	lowerCamelCase_      ,	)
     UpperCAmelCase_				:  List[str]  = 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()






