Wafu!

The operation looks chaotic, but the minimum rule makes it extremely structured.

Suppose the initial values are sorted:

$a_1<a_2<\dots<a_n.$

When $a_j$ becomes the minimum, all smaller generated values have already been removed, and all remaining original values are larger. So the next operation removes $a_j$, then inserts

$1,2,\dots,a_j-1.$

Those inserted values are all smaller than every remaining original value, so they must be fully processed before we ever touch $a_{j+1}$. That means each original value $x$ contributes one independent block:

$B_x = x, F_{x-1},$

where $F_r$ is the full removal sequence starting from the set $\{1,2,\dots,r\}$.

So the whole answer is just the product of the first $k$ values in

$B_{a_1}, B_{a_2}, \dots, B_{a_n}.$

The problem is now: how do we understand $F_r$ without simulating a billion operations like a cursed spreadsheet?

The key recurrence

Look at $F_r$, starting from $\{1,2,\dots,r\}$.

The value $r$ is the largest, so it cannot be removed until every value $1,2,\dots,r-1$ is gone. The sequence before removing $r$ is exactly $F_{r-1}$.

Then we remove $r$, and the operation inserts $1,2,\dots,r-1$ again. That creates another copy of $F_{r-1}$.

Therefore:

$F_r = F_{r-1},\ r,\ F_{r-1}.$

This gives two useful facts immediately.

Length:

$L_0=0,$

$L_r=2L_{r-1}+1=2^r-1.$

Full product:

$P_0=1,$

$P_r=P_{r-1}^2\cdot r.$

We precompute $L_r$ and $P_r$ for about $r\le 31$, because $k\le 10^9$ and $2^{30}>10^9$. Big numbers in the statement are mostly there to scare you. Rude, but fair.

Processing original blocks

For an original value $x$, its block is

$B_x=x,F_{x-1}.$

So:

$|B_x|=1+|F_{x-1}|=2^{x-1},$

and the product of the whole block is

$x\cdot P_{x-1}.$

We sort the initial array and walk through it. If the whole block fits inside the remaining $k$, multiply the answer by its full product and subtract its length.

If the block does not fully fit, then this is the final block we need. We multiply by $x$, subtract one operation, and then need the prefix product of $F_{x-1}$ for the remaining number of operations.

Prefix product of $F_r$

Use the recurrence:

$F_r=F_{r-1},r,F_{r-1}.$

To compute the product of the first $q$ elements of $F_r$:

• If $q\le L_{r-1}$, it lies entirely in the first $F_{r-1}$.
• Otherwise, multiply by all of the first $F_{r-1}$ and by $r$.
• If there is still leftover, recurse into the second $F_{r-1}$.

For huge $r$, the first $q$ elements do not even reach the large values. We can clamp $r$ down to the smallest value with $L_r\ge q$, which is at most $30$.

So every prefix query is only $O(30)$.

Complexity

Sorting dominates:

$O(n\log n)$

per test case, with total $n\le 2\cdot 10^5$.

Memory is $O(1)$ besides the input array.