解説

バター泥棒は，自分が盗むことができるバターのうち美味しさが最も大きいものを盗む代わりに，盗むことができるバターをすべて盗むことにします．
こうすることで，バター泥棒が盗むバターの番号の代わりに，盗むバターの個数を考えれば良いことになります．
（例：レベル $5$ のバター泥棒は $4$ 番目の美味しさ $5$ のバターを盗む → レベル $5$ のバター泥棒は美味しさ $1,2,3,5$ のバター計 $4$ 個を盗む）

$f(X)$ を以下のように定義すると，答えは $f(R)-f(L-1)$ です．ただし，$f(0)=0$ とします．

• $f(X)=$ レベル $1,2,\dots,X$ のバター泥棒が $1$ 人ずつ現れ Sakky さんを襲うときの盗むバターの個数の総和

$f(X)$ を求めましょう．「各バター泥棒はどのバターを盗むか」という見方を変えて「各バターはどのバター泥棒に盗まれるか」を考えると，

• $i$ 番目のバターは，レベルが $F_i$ 以上のバター泥棒に盗まれる

ということが分かります．よって，

• $f(X)=\displaystyle\sum_{i=1}^{10^{100}}\max(0,X-F_i+1)$

が成り立ちます．$F_{78}=14472334024676221>10^{16}$ であることから，$\sum$ を計算する時には $i\le 77$ の範囲のみを考えれば十分です．