E. Mahmoud and Ehab and the xor-MST

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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). Can you find the weight of the minimum spanning tree of that graph?

You can read about complete graphs in

You can read about the minimum spanning tree in

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.

Input

The only line contains an integer n (2 ≤ n ≤ 1012), the number of vertices in the graph.

Output

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

Example

Input

Copy

4

Output

Copy

4

解析:每个二进制位会贡献当前总数/2这么多的贡献 然后也相当于合并了这么些连通块 然后用总数减去合并的这些连通块再重复以上步骤

#include
    
     #define ll long long#define inf 0x3f3f3f3f#define pb push_back#define rep(i,a,b) for(int i=a;i<=b;i++)#define rep1(i,b,a) for(int i=b;i>=a;i--)using namespace std;const int N=1e5+100;ll arr[N];int main(){    ll n,ans=0,base=1;    cin>>n;    while(n>1)    {        ans+=base*(n>>1);        base<<=1;        n-=n>>1;    }    cout<
     
      <