given $$$n$$$ segments $$$[l_i, r_i]$$$ where $$$-10^9 \leq l, r \leq 10^9$$$. we are given $$$q$$$ query. each query characterized by one integer $$$x$$$. for each query we must determine how many segment involves $$$x$$$ and detect segments itself by its number. How to solve this problem?

see tutorial about stern-brocot's tree Tutorial. this is infinity binary tree which nodes are irreducible fractions. enumerate nodes of tree using BFS. it is given one number n and one fraction . Your task is to determine what fraction is written on the node LCA(n, ) where LCA is Lowest Common Ancestor of nodes n and . (in first case node is defined by its number and in second case node is defined by fraction). 0 < a, b < 10⁹ and 0 < n < 10¹⁸.

what is efficient method for finding what fraction is written on the node by its fraction and vice versa?