
from __future__ import annotations

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







class 	lowerCamelCase						:





     def __init__(self :       List[str]							,       _A :       int  )		->		None:
         snake_case						=   -1
         snake_case						=   -1
         snake_case						=   [-1] * length
         snake_case						=   None
         snake_case						=   None





     def __repr__(self :       Dict  )		->		str:
         return f'Node(min_value={self.minn} max_value={self.maxx})'



def 		lowercase_     (  A__						)				->				Node | None:
    """simple docstring"""

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

    snake_case						=   []
    snake_case						=   []

    for index, num in enumerate(A__						):
        if num <= pivot:
            left_arr.append(A__						)
        else:
            right_arr.append(A__						)
        snake_case						=   len(A__						)
    snake_case						=   build_tree(A__						)
    snake_case						=   build_tree(A__						)
    return root



def 		lowercase_     (  A__					,						A__					,						A__						)				->				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
    snake_case						=   (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 		lowercase_     (  A__					,						A__					,						A__					,						A__						)				->				int:
    """simple docstring"""

    if start > end:
        return 0
    snake_case						=   rank_till_index(A__					,						A__					,						A__						)
    snake_case						=   rank_till_index(A__					,						A__					,						start - 1						)
    return rank_till_end - rank_before_start



def 		lowercase_     (  A__					,						A__					,						A__					,						A__						)				->				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]
    snake_case						=   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 		lowercase_     (  A__					,						A__					,						A__					,						A__					,						A__						)				->				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
    snake_case						=   range_counting(
        node.left					,						(node.map_left[start - 1] if start else 0)					,						node.map_left[end] - 1					,						A__					,						A__					,						)
    snake_case						=   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()



_A       =					{
    "0": 1,
    "1": 1,
    "2": 2,
    "3": 6,
    "4": 24,
    "5": 1_20,
    "6": 7_20,
    "7": 50_40,
    "8": 4_03_20,
    "9": 36_28_80,
}

_A       =					{1_45: 1_45}

_A       =					{
    1_45: 0,
    1_69: 3,
    3_63_01: 3,
    14_54: 3,
    8_71: 2,
    4_53_61: 2,
    8_72: 2,
}



def 		lowercase_     (  A__						)				->				int:
    """simple docstring"""

    if n in CACHE_SUM_DIGIT_FACTORIALS:
        return CACHE_SUM_DIGIT_FACTORIALS[n]
    snake_case						=   sum(DIGIT_FACTORIALS[let] for let in str(A__						)						)
    snake_case						=   ret
    return ret



def 		lowercase_     (  A__					,						A__ = None						)				->				int:
    """simple docstring"""

    snake_case						=   previous or set()
    if n in CHAIN_LENGTH_CACHE:
        return CHAIN_LENGTH_CACHE[n]
    snake_case						=   sum_digit_factorials(A__						)
    if next_number in previous:
        snake_case						=   0
        return 0
    else:
        previous.add(A__						)
        snake_case						=   1 + chain_length(A__					,						A__						)
        snake_case						=   ret
        return ret



def 		lowercase_     (  A__ = 60					,						A__ = 100_0000						)				->				int:
    """simple docstring"""

    return sum(1 for i in range(1					,						A__						) if chain_length(A__						) == num_terms						)


if __name__ == "__main__":
   print(f"{solution() = }")

