Sum of Maximum Array Indices in Segment Tree Construction

Chino has just learned a data structure called the segment tree. However, when implementing it she encountered a problem: she does not know the amount of space to allocate. She only knows that the number of leaf nodes (n) is an integer in the range ([a, b]).

Let (f(n)) be the maximum array index used when constructing a segment tree with (n) leaves by calling the function

[ \textbf{BuildSegmentTree}(1, 1, n), , ]

according to the following pseudocode:

$$\begin{array}{l} \textbf{Function: } BuildSegmentTree(x, l, r):\\ \quad \textbf{if } (l \ne r) \textbf{ then}\\ \quad \quad m \gets \lfloor (l + r)/2 \rfloor.\\ \quad \quad BuildSegmentTree(2x, l, m).\\ \quad \quad BuildSegmentTree(2x+1, m+1, r).\\ \quad \textbf{end if}\\ \quad \textbf{return} \; (\text{implicitly, the maximum value of } x \text{ seen in all calls}). \end{array} $$

The value (f(n)) is defined as the maximum value of the parameter (x) among all calls to (BuildSegmentTree) when constructing the tree. Chino believes that if she knows

$$\sum_{n=a}^{b} f(n),$$

she will be able to determine the required space. Your task is to help her compute this sum given the range (a) to (b).

Note: In the pseudocode, the function recursively assigns indices as in a binary heap: the left child of node (x) is (2x) and the right child is (2x+1). The tree is built only for the intervals where (l \ne r), and when (l = r) the recursion stops. The maximum index over all recursive calls is (f(n)).

Input Format: Two integers (a) and (b) separated by space, where (1 \leq a \leq b).

Output Format: Output a single integer which is (\sum_{n=a}^{b} f(n)).

inputFormat

The input consists of a single line containing two space‐separated integers a and b (with 1 ≤ a ≤ b), representing the range for the number of leaf nodes.

outputFormat

Output a single integer which is the sum \(\sum_{n=a}^{b} f(n)\), where \(f(n)\) is the maximum array index used during the segment tree construction for n leaves.

sample

1 1

1