Mahmoud and Ehab and the xor-MST

题意翻译

- 一完全图有 $n$ 个节点 $0,...,n-1$，其中边 $(i,j)$ 的权值为 $i\oplus j$，其中 $\oplus$ 为位异或操作，试求出最小生成树的边权和。 - $2\leq n\leq 10^{12}$。

题目描述

Ehab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of $ n $ vertices numbered from $ 0 $ to $ n-1 $ . For all $ 0<=u<v<n $ , vertex $ u $ and vertex $ v $ are connected with an undirected edge that has weight  (where  is the [bitwise-xor operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)). Can you find the weight of the minimum spanning tree of that graph? You can read about complete graphs in [https://en.wikipedia.org/wiki/Complete\_graph](https://en.wikipedia.org/wiki/Complete_graph) You can read about the minimum spanning tree in [https://en.wikipedia.org/wiki/Minimum\_spanning\_tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree) The weight of the minimum spanning tree is the sum of the weights on the edges included in it.

输入输出格式

输入格式

The only line contains an integer $ n $ $ (2<=n<=10^{12}) $ , the number of vertices in the graph.

输出格式

The only line contains an integer $ x $ , the weight of the graph's minimum spanning tree.

输入输出样例

输入样例 #1

4

输出样例 #1

4

说明

In the first sample:  The weight of the minimum spanning tree is 1+2+1=4.