Consider a standard binary heap, as described e.g. in this Wikipedia article revision.
We have a tree with \(n\) empty nodes that has the shape of a \(n\)-element binary heap. We are going to place the values \(1\) through \(n\) into the nodes in such a way that they form a max-heap.
Let \(c_x\) be the number of nodes that can contain the value \(x\).
Determine the values \(c_x\). Then, calculate and output the value \(\sum_{i=1}^n i\cdot c_i\).
The first line of each input file contains the number \(t\) of test cases. The specified number of test cases follows, one after another.
Each test case consists of a single line with a single positive integer \(n\). Each test has \(n\leq 2\,500\,000\).
For each test case output a single line with a single integer. Ideally, that integer should be the value of the sum defined above.
You may assume that the correct answer for each test case fits into a signed 64-bit integer variable.
Input file: H1.in
There is a single input file for this problem. You may submit output files in which some of the outputs are incorrect and still receive a partial score. (E.g., you may output \(-1\) instead of the correct answer for tests that you don’t want to solve.)
Your output file must contain exactly \(t\) integers. If it contains anything else, you will score zero.
Your score will be computed by adding up the following:
input3 2 3 4 | output3 9 18 |
For \(n=2\) the value \(2\) must be in the root and the value \(1\) must be in its only child. Each value has a single position where it can appear, hence \(c_1=c_2=1\).
For \(n=3\) the value \(3\) must be in the root and the other two values in the leaves, in either order. Hence, \(c_3=1\) but \(c_1=c_2=2\). The answer is \(1\cdot 2 + 2\cdot 2 + 3\cdot 1\).
For \(n=4\) we have \(c_1=2\), \(c_2=3\), \(c_3=2\), and \(c_4=1\).
