{"raw_statement":[{"iden":"statement","content":"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?\n\nYou can read about complete graphs in [https://en.wikipedia.org/wiki/Complete_graph](https://en.wikipedia.org/wiki/Complete_graph)\n\nYou can read about the minimum spanning tree in [https://en.wikipedia.org/wiki/Minimum_spanning_tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree)\n\nThe weight of the minimum spanning tree is the sum of the weights on the edges included in it."},{"iden":"input","content":"The only line contains an integer _n_ (2 ≤ _n_ ≤ 1012), the number of vertices in the graph."},{"iden":"output","content":"The only line contains an integer _x_, the weight of the graph's minimum spanning tree."},{"iden":"example","content":"Input\n\n4\n\nOutput\n\n4"},{"iden":"note","content":"In the first sample: ![image](https://espresso.codeforces.com/4946726fa48431a5ac5abcbb96045299d81c25fe.png) The weight of the minimum spanning tree is 1+2+1=4."}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"Ehab 对按位异或运算和特殊图感兴趣。Mahmoud 给了他一个结合了这两者的问题。他有一个包含 #cf_span[n] 个顶点的完全图，顶点编号从 #cf_span[0] 到 #cf_span[n - 1]。对于所有 #cf_span[0 ≤ u < v < n]，顶点 #cf_span[u] 和顶点 #cf_span[v] 通过一条无向边连接，该边的权重为 #cf_span[u \\oplus v]（其中 \\oplus 是按位异或运算）。你能找出该图的最小生成树的权重吗？\\n\\n你可以阅读有关完全图的信息：https://en.wikipedia.org/wiki/Complete_graph\\n\\n你可以阅读有关最小生成树的信息：https://en.wikipedia.org/wiki/Minimum_spanning_tree\\n\\n最小生成树的权重是其中包含的所有边的权重之和。\\n\\n输入仅包含一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 10^{12})]，表示图中顶点的数量。\\n\\n输出仅包含一个整数 #cf_span[x]，表示该图最小生成树的权重。\\n\\n在第一个样例中：最小生成树的权重为 1+2+1=4。\"},{\"iden\":\"input\",\"content\":\"输入仅包含一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 10^{12})]，表示图中顶点的数量。\"},{\"iden\":\"output\",\"content\":\"输出仅包含一个整数 #cf_span[x]，表示该图最小生成树的权重。\"},{\"iden\":\"note\",\"content\":\"在第一个样例中：最小生成树的权重为 1+2+1=4。\"}]","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 10^{12} $.  \nConsider the complete graph $ G = (V, E) $ where:  \n- $ V = \\{0, 1, 2, \\dots, n-1\\} $,  \n- For every pair $ u, v \\in V $ with $ u < v $, there is an undirected edge $ (u, v) \\in E $ with weight $ u \\oplus v $, where $ \\oplus $ denotes bitwise XOR.\n\n**Objective**  \nCompute the total weight of the minimum spanning tree (MST) of $ G $.\n\n**Constraints**  \n$ 2 \\leq n \\leq 10^{12} $","simple_statement":null,"has_page_source":false}