CF768B.Code For 1

Jon fought bravely to rescue the wildlings who were attacked by the white-walkers at Hardhome. On his arrival, Sam tells him that he wants to go to Oldtown to train at the Citadel to become a maester, so he can return and take the deceased Aemon's place as maester of Castle Black. Jon agrees to Sam's proposal and Sam sets off his journey to the Citadel. However becoming a trainee at the Citadel is not a cakewalk and hence the maesters at the Citadel gave Sam a problem to test his eligibility.

Initially Sam has a list with a single element n. Then he has to perform certain operations on this list. In each operation Sam must remove any element x, such that x > 1, from the list and insert at the same position , , sequentially. He must continue with these operations until all the elements in the list are either 0 or 1.

Now the masters want the total number of 1s in the range l to r (1-indexed). Sam wants to become a maester but unfortunately he cannot solve this problem. Can you help Sam to pass the eligibility test?

琼恩英勇奋战，解救了在硬堡遭异鬼袭击的自由民。他抵达后，山姆告诉他，自己想去旧镇的学城接受训练，成为一名学士，以便归来接替已故的伊蒙学士，成为黑城堡的学士。琼恩同意了山姆的请求，山姆随即启程前往学城。然而，要成为学城的一名见习学士绝非易事，因此学城的学士们给山姆出了一道题，以测试他的资格。

最初，山姆手中有一个仅含单个元素 $n$ 的列表。接着，他需要对该列表执行若干次操作。在每次操作中，山姆必须从列表中移除任意一个满足 $x > 1$ 的元素 $x$，并在原位置依次插入
、
、
。
他必须持续进行这些操作，直到列表中的所有元素均为 $0$ 或 $1$。

现在，学士们要求计算最终列表中第 $l$ 到第 $r$ 个位置（按 1-索引）之间所有 $1$ 的总数。山姆渴望成为学士，却不幸无法解出这道题。你能帮助山姆通过这项资格测试吗？

The first line contains three integers n, l, r (0 ≤ n < 250, 0 ≤ r - l ≤ 105, r ≥ 1, l ≥ 1) – initial element and the range l to r.

It is guaranteed that r is not greater than the length of the final list.

第一行包含三个整数 $n$、$l$、$r$（$0 ≤ n < 250$，$0 ≤ r - l ≤ 10^5$，$r ≥ 1$，$l ≥ 1$）——初始元素以及范围 $l$ 到 $r$。

保证 $r$ 不超过最终列表的长度。

Output the total number of 1s in the range l to r in the final sequence.

输出最终序列中区间 $l$ 到 $r$ 内数字 1 的总数。

Consider first example:

Elements on positions from 2-nd to 5-th in list is [1, 1, 1, 1]. The number of ones is 4.

For the second example:

Elements on positions from 3-rd to 10-th in list is [1, 1, 1, 0, 1, 0, 1, 0]. The number of ones is 5.

先考虑第一个例子：

列表中第 2 至第 5 个位置上的元素为 [1, 1, 1, 1]，其中 1 的个数为 4。

对于第二个例子：

列表中第 3 至第 10 个位置上的元素为 [1, 1, 1, 0, 1, 0, 1, 0]，其中 1 的个数为 5。