No Mind To Think

Sort the array first. This is not a positional problem; the subsequence condition just means “pick any multiset of currently existing values.” After every operation we could sort again and nothing changes except making the reasoning less cursed.

Let the sorted array be

$a_0 \le a_1 \le \dots \le a_{n-1}.$

Choose an odd operation size

$x=2y+1.$

So every operation has $y$ values below/equal the median, one median value, and $y$ values above/equal the median.

One fixed operation

Suppose an operation has median $a_i$. Then, in sorted-value language, it should use:

$a_0,a_1,\dots,a_{y-1},\quad a_i,\quad a_{i+1},a_{i+2},\dots,a_{i+y}$

if we are only looking at one operation.

Why? The left side gets increased to $a_i$, so we want the smallest values possible there. The right side gets decreased to $a_i$, so we want the smallest values larger than the median there, i.e. the closest ones. Picking bigger right-side values is just donating points to the void. Bad trade.

For this to be legal, we need

$0 \le y \le \min(i,n-i-1).$

Why one median is enough

Fix $y$. Imagine using two operations with medians $a_i$ and $a_j$, where $i<j$.

The lower median $a_i$ can only raise some small values up to $a_i$. If we instead use $a_j$, those same small values can be raised to something at least as large. Also, the operation with median $a_i$ forces some values after $i$ to drop to $a_i$. Replacing it with another operation of median $a_j$ does not create a worse forced decrease: the right-side support for $a_j$ can be reused.

So lower medians are never essential. Repeating this argument, for a fixed $y$ there is an optimal strategy where all operations use one median value $a_i$.

That is the key simplification. Without it, this problem looks like subset soup. With it, it becomes a sorted-array optimization.

Value for fixed median and fixed $y$

Fix median index $i$ and operation parameter $y$.

Across at most $k$ operations, each operation can raise up to $y$ small values to $a_i$. Therefore we can raise

$q=\min(ky,i)$

values before $i$.

The best values to raise are the smallest ones:

$a_0,a_1,\dots,a_{q-1}.$

The right support values only need to be decreased once, and they should be

$a_{i+1},a_{i+2},\dots,a_{i+y}.$

So the improvement is

$q\cdot a_i - \sum_{p=0}^{q-1}a_p + y\cdot a_i - \sum_{p=i+1}^{i+y}a_p.$

Equivalently,

$\text{gain}(i,y)=(q+y)a_i-\sum_{p=0}^{q-1}a_p-\sum_{p=i+1}^{i+y}a_p.$

The answer is the original sum plus the maximum nonnegative gain over all $i,y$. Taking $y=0$ means $x=1$, which changes nothing, so the original sum is always available.

Optimizing $y$ for one median

Trying every $y$ for every $i$ would be $O(n^2)$, which is dead on arrival.

For fixed $i$, look at the marginal gain from increasing $y-1$ to $y$.

When $y$ increases by $1$:

• we may raise up to $k$ more left-side values to $a_i$;
• we must also decrease one more right-side value, namely $a_{i+y}$, to $a_i$.

The newly raised left-side values are farther right than before, so they are larger or equal, meaning their benefit is smaller or equal. The newly decreased right-side value is also farther right, so its loss is larger or equal. Therefore the marginal gain is monotonically nonincreasing.

That means $\text{gain}(i,y)$ is unimodal/concave-ish over integer $y$: keep increasing $y$ while the marginal gain is nonnegative, then stop. Binary search finds that last good $y$.

For a candidate $y\ge1$, define

$L=\min((y-1)k,i),$

$R=\min(yk-1,i).$

The indices $L\dots R$ are the newly added left-side values. If all true left values are already used, this range may include $a_i$ itself as a dummy zero-gain value. That is fine and keeps the formula clean.

The marginal gain is nonnegative iff

$\sum_{p=L}^{R}(a_i-a_p)+(a_i-a_{i+y})\ge 0.$

Rearrange it into the code-friendly check:

$\sum_{p=L}^{R}a_p+a_{i+y}\le (R-L+2)a_i.$

All range sums come from prefix sums, so each check is $O(1)$.

For every median index $i$, binary search $y$ in

$[1,\min(i,n-i-1)].$

Total complexity:

$O(n\log n)$

per test case after sorting, easily fine for $\sum n\le 2\cdot 10^5$.