题目描述

有一个序列，初始时序列中只包含一个数值为 $n$ 的元素。

然后，这个序列会进行若干轮转换，每轮转换，对于序列中数值大于 $1$ 的任意元素 $x$，它都会转换成 $3$ 个整数 $\lfloor \frac{x}{2} \rfloor$，$x \text{ mod } 2$，$\lfloor \frac{x}{2} \rfloor$。（也就是说，$x$ 会消失，同时在 $x$ 所在的位置会依次加入三个整数 $\lfloor \frac{x}{2} \rfloor$，$x \text{ mod } 2$ 和 $\lfloor \frac{x}{2} \rfloor$；这里 $\lfloor \frac{x}{2} \rfloor$ 表示 $\frac{x}{2}$ 向下取整的结果，$x \text{ mod } 2$ 表示 $x$ 除以 $2$ 的余数）

序列会一直进行转换，直至序列中所有元素的数值都 $\le 1$。

对于最终的序列，你需要求出：序列中第 $l$ 个元素到第 $r$ 个元素（包括第 $l$ 和第 $r$ 个元素）的数值之和。

举一些例子：

若 $n = 7$，则序列的变化过程为：$[\ 7 \ ]$ $\rightarrow [\ 3, 1, 3 \ ]$ $\rightarrow [\ 1,1,1,1,1,1,1 \ ]$

若 $n = 10$，则序列的变化过程为：$[\ 10 \ ]$$[\ 5, 0, 5 \ ]$ $\rightarrow [\ 2, 1, 2, 0, 2, 1, 2 \ ]$ $\rightarrow [\ 1,0,1,1,1,0,1,0,1,0,1,1,1,0,1 \ ]$

输入格式

输入共一行，包含三个整数 $n, l, r$，两两之间以一个空格分隔（$0 \le n \lt 2^{50}$, $1 \le l \le r$ 且 $r - l \le 10^5$ 且 $r$ 不大于最终序列的长度）。

输出格式

输出一个整数，表示最终序列从第 $l$ 个元素到第 $r$ 个元素（包括第 $l$ 个元素和第 $r$ 个元素）范围内所有数字之和。

7 2 5

4

10 3 10

5

说明/提示

样例解释

样例1：

$[\ 7 \ ]$ $\rightarrow [\ 3, 1, 3 \ ]$ $\rightarrow [\ 1,1,1,1,1,1,1 \ ]$

最终序列的第 $2$ 到 $5$ 个元素为：$[\ 1, 1, 1, 1\ ]$，对应的元素和为 $4$。

样例2：

$[\ 10 \ ]$$[\ 5, 0, 5 \ ]$ $\rightarrow [\ 2, 1, 2, 0, 2, 1, 2 \ ]$ $\rightarrow [\ 1,0,1,1,1,0,1,0,1,0,1,1,1,0,1 \ ]$

最终序列的第 $3$ 到 $10$ 个元素为 $[\ 1, 1, 1, 0, 1, 0, 1, 0 \ ]$，对应的元素和为 $5$。

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 1000, r - l \le 10$；
• 对于 $60\%$ 的数据，$n \le 10^6, r - l \le 10^3$；
• 对于 $100\%$ 的数据，$0 \le n \lt 2^{50}$, $1 \le l \le r$ 且 $r - l \le 10^5$ 且 $r$ 不大于最终序列的长度。