← 返回题目列表

Codeforces · 959/E

E. Mahmoud 和 Ehab 以及 xor-MST

中文机器翻译题面 查看原题

Ehab 对按位异或运算和特殊图感兴趣。马哈茂德给了他一个结合了两者的问题。他有一个完整的图,由编号为 0 到 n - 1 的 n 个顶点组成。对于所有 0 ≤ u < v < n,顶点 u 和顶点 v 与权重为 $$u \oplus v$$ 的无向边连接(其中 $$\bigcirc$$ 是按位异或运算)。你能找到该图的最小生成树的权重吗?

您可以在 https://en.wikipedia.org/wiki/Complete_graph 中阅读完整图表

您可以在 https://en.wikipedia.org/wiki/Minimum_spanning_tree 中阅读有关最小生成树的信息

最小生成树的权重是其中包含的边上的权重之和。

输入

唯一一行包含整数 n (2 ≤ n ≤ 1012),即图中的顶点数。

输出

唯一的一行包含一个整数 x,即图的最小生成树的权重。

示例

输入 #1

4

输出 #1

4

注意

第一个样本中:最小生成树的权重为1+2+1=4。