"""simple docstring"""


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 					a					:



  def __init__(		self   :    Union[str, Any]						,  lowerCamelCase_   :    int     )      -> None:
      __a			      =						-1
      __a			      =						-1
      __a			      =						[-1] * length
      __a			      =						None
      __a			      =						None



  def __repr__(		self   :    Union[str, Any]     )      -> str:
      return F"""Node(min_value={self.minn} max_value={self.maxx})"""

def 						UpperCamelCase				(	_lowerCAmelCase   :							list[int]						):
    __a			      =						Node(len(_lowerCAmelCase						)						)
    __a      ,  __a			      =						min(_lowerCAmelCase						), max(_lowerCAmelCase						)
    # Leaf node case where the node contains only one unique value
    if root.minn == root.maxx:
        return root
    __a			      =						(root.minn + root.maxx) // 2

    __a			      =						[]
    __a			      =						[]

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

def 						UpperCamelCase				(	_lowerCAmelCase   :							Node | None				, _lowerCAmelCase   :							int				, _lowerCAmelCase   :							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
    __a			      =						(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 						UpperCamelCase				(	_lowerCAmelCase   :							Node | None				, _lowerCAmelCase   :							int				, _lowerCAmelCase   :							int				, _lowerCAmelCase   :							int						):
    if start > end:
        return 0
    __a			      =						rank_till_index(_lowerCAmelCase				, _lowerCAmelCase				, _lowerCAmelCase						)
    __a			      =						rank_till_index(_lowerCAmelCase				, _lowerCAmelCase				, start - 1						)
    return rank_till_end - rank_before_start

def 						UpperCamelCase				(	_lowerCAmelCase   :							Node | None				, _lowerCAmelCase   :							int				, _lowerCAmelCase   :							int				, _lowerCAmelCase   :							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]
    __a			      =						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 						UpperCamelCase				(	_lowerCAmelCase   :							Node | None				, _lowerCAmelCase   :							int				, _lowerCAmelCase   :							int				, _lowerCAmelCase   :							int				, _lowerCAmelCase   :							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
    __a			      =						range_counting(
        node.left				, (node.map_left[start - 1] if start else 0)				, node.map_left[end] - 1				, _lowerCAmelCase				, _lowerCAmelCase				, )
    __a			      =						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()

"""simple docstring"""


from doctest import testmod
from math import sqrt

def 						UpperCamelCase				(	_lowerCAmelCase   :							int						):
    __a			      =						[]
    if num < 1:
        return facs
    facs.append(1						)
    if num == 1:
        return facs
    facs.append(_lowerCAmelCase						)
    for i in range(2				, int(sqrt(_lowerCAmelCase						)						) + 1						):
        if num % i == 0:  # If i is a factor of num
            facs.append(_lowerCAmelCase						)
            __a			      =						num // i  # num//i is the other factor of num
            if d != i:  # If d and i are distinct
                facs.append(_lowerCAmelCase						)  # we have found another factor
    facs.sort()
    return facs


if __name__ == "__main__":
 testmod(name="""factors_of_a_number""", verbose=True)
