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。