Operations on stacks of coins I'm struggling with a problem from some old programming contest with no result, so I'm asking for help here. Let me describe it below.
At first we have $1\le n\le1000$ stacks of coins, each of them contains at most $10^9$ coins. Then in one move we select the highest stack (if there are many with maximal number of coins, we select one of them) and let's say that it has $m$ coins. Then we split it into two stacks containing $m$ div 2 and ($m$+1) div 2 coins respectively. We make moves until there are only stacks with $1$ coin.
So the input for this problem is a number $n$ and then $n$ numbers describing initial heights of those stacks. Then there is a number $1\le q\le 5*10^5$ which denotes number of queries. Each query consists of one number $1\le k\le 10^9$. So we have $q$ queries, respectively: $k_1, k_2,..., k_q$ and we know that the sum of those numbers is less or equal the number of possible moves until end condition. For number $k_1$ we have to print the number of different heights of stacks after $k_1$ moves. For number $k_2$ we have to print the number of different heights of stacks after next $k_2$ moves, and so on.
This problem would be easy if it wasn't for possible big initial heights of stacks ($10^9$).
For example, we have $3$ stacks with $9, 2$ and $8$ coins respectively, at first. Then for query input (first number is a number q): $3, 1, 2, 3$, the correct output is: $4, 3, 2$, because after first move we have stacks: $8,5,4,2$, after three moves we have: $4,4,4,3,2$ (three different heights), and after $1+2+3=6$ moves we have: $3,2,2,2,2,2,2,2,2$.
Can anybody help? How can I solve this fast? (standard time limit 1sec for one test file and 256MB RAM, something like $O(q\log q)$ should be fine).
 A: Up to order of operations, the way a particular stack is split is independent from the others.

Theorem: At every step, each one of the original stacks has at most $3$ different children.

Proof: Denote $[y]$ to be a stack of $y$ coins, $
\xrightarrow{N}$ to be $N$ iterations of the algorithm(if $N$ is missing assume one iteration) and $*$ to be an arbirtary number.
Setting $k=2^m(2n+1)$ to be the amout of coins in a particular stack, we have
$$[2^m(2n+1)] \rightarrow 2[2^{m-1}(2n+1)]\rightarrow2[2^{m-2}(2n+1)],[2^{m-1}(2n+1)]$$
$$\rightarrow4[2^{m-2}(2n+1)]$$
By induction we can verify that at every step there are at most $2$ different children, and that
$$[2^m(2n+1)] \xrightarrow{2^{m}-1} 2^m[2n+1]\tag1$$
So we have $2^m$ equal stacks of $2n+1$ coins each. Analyzing only one of them:
$$[2n+1]\rightarrow[n],[n+1]$$
If $n=2q$
$$[2q],[2q+1]\rightarrow[2q],[q+1],[q]\rightarrow 3[q],[q+1]$$
$$\implies a[2q],b[2q+1]\xrightarrow{a+b} (2a+b)[q],b[q+1]\tag2$$
If $n=2q+1$
$$[2q+1],[2q+2]\rightarrow[2q+1],2[q+1]\rightarrow [q],3[q+1]$$
$$\implies a[2q+1],b[2q+2]\xrightarrow{a+b} a[q],(a+2b)[q+1]\tag3$$
So in general $a[x],b[x+1]\xrightarrow{*}c[y],d[y+1]$, where $x>y$(we can deal with the case $a[1],b[2]$ easily) and at every step there is at most three diferent stacks.
Conclusion: Processes $(1),(2),(3)$, are immediate, that is, they can be done consecutively without switching our attention to other stacks(why?), allowing us to apply all those iterations at once (becomes especially useful when the coefficients $a,b$ get large). Therefore we can just massively jump those intermediate steps with $3$ different stacks. Anyway, depending on the query we are given we may stop mid-process. Finally, it would suffice to create a data structure for each of the stacks so that it can hold integers $a,b,c,x,y,z$ to represent $a[x],b[y],c[z]$.
