琼恩勇敢地战斗,营救在艰难家园被异鬼袭击的野人。到达后,山姆告诉他,他想去旧镇在学城接受训练,成为一名学士,这样他就可以回来接替已故的伊蒙,成为黑城堡的学士。琼恩同意了山姆的提议,山姆踏上了前往城堡的旅程。然而,成为神堡的实习生并不是一件容易的事,因此神堡的学士们给山姆出了一个问题来测试他的资格。
最初 Sam 有一个包含单个元素 n 的列表。然后他必须对该列表执行某些操作。在每个操作中,Sam 必须从列表中删除任何 x > 1 的元素 x,并按顺序在同一位置插入 $$\left\lfloor \frac{x}{2} \right\rfloor$$、$$x \mod 2$$、$$\left\lfloor \frac{x}{2} \right\rfloor$$。他必须继续这些操作,直到列表中的所有元素都为 0 或 1。
现在主设备想要 l 到 r(1 索引)范围内的 1 总数。山姆想成为一名学士,但不幸的是他无法解决这个问题。你能帮助山姆通过资格测试吗?
输入
第一行包含三个整数 n、l、r (0 ≤ n < 250, 0 ≤ r - l ≤ 105, r ≥ 1, l ≥ 1) – 初始元素和范围 l 到 r。
保证r不大于最终列表的长度。
输出
输出最终序列中l到r范围内1的总数。
示例
输入 #1
7 2 5
输出 #1
4
输入 #2
10 3 10
输出 #2
5
注意
考虑第一个例子:
$$[7] \rightarrow [3,1,3] \rightarrow [1,1,1,1,3] \rightarrow [1,1,1,1,1,1] \rightarrow [1,1,1,1,1,1]$$
列表中第 2 到 5 个位置上的元素为 [1, 1, 1, 1]。数量是 4。
对于第二个示例:
$$[10] \rightarrow [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1]$$
列表中第 3 到第 10 位置的元素为 [1, 1, 1, 0, 1, 0, 1, 0]。数量是 5。