Mexification

The operation looks index-based, but that is mostly bait. The value of an element after an operation depends on only two things:

• the MEX of the whole current array
• whether this element is the only copy of a small value

The fact that everything updates simultaneously matters. We always reason from the old counts, not from half-updated garbage.

One Operation Exactly

Let $m$ be the MEX of the current array. That means:

• every value $0,1,\dots,m-1$ appears at least once
• value $m$ does not appear

Now take an element with value $x$ and remove it temporarily.

If $x<m$ and $x$ appeared exactly once, then removing it makes $x$ missing. All smaller values still exist, so the MEX of the remaining array is $x$.

Otherwise, removing this element does not break the presence of all values $0,1,\dots,m-1$. Since $m$ was already missing, it is still missing. So the MEX is still $m$.

So the new value is:

$$\begin{cases} x, & x<m \text{ and } cnt[x]=1 \\ m, & \text{otherwise} \end{cases}$$

That's the whole problem. Seriously. The rest is just not messing up the parity.

Therefore, after the first operation:

• every uniquely occurring value below $m$ survives
• every duplicated value below $m$ disappears
• every value above $m$ becomes $m$
• all the other elements become copies of $m$

The sum after one operation is easy:

$$\sum_{x<m,\ cnt[x]=1} x + m\cdot\left(n - \#\{x<m:cnt[x]=1\}\right)$$

If $k=1$, we are done.

What Happens After That?

Now find the first duplicated value below the original MEX:

$$p = \min\{x<m : cnt[x]>1\}$$

There are two cases.

Case 1: A duplicated small value exists

Suppose this first duplicated value is $p$.

After the first operation, $p$ disappears, because duplicated values below $m$ do not survive. Every value below $p$ was not duplicated, because $p$ was the first duplicated one, so $0,1,\dots,p-1$ are still present exactly once.

So the new MEX becomes $p$.

After one more operation, only those unique values $0,1,\dots,p-1$ stay, and every other element becomes $p$.

So at operation $2$, the array has this clean form:

$$[0,1,2,\dots,p-1,\underbrace{p,p,\dots,p}_{n-p\text{ copies}}]$$

Call this the low state.

Case 2: No duplicated small value exists

Then all values $0,1,\dots,m-1$ occur exactly once.

After the first operation, those values stay, and every other element becomes $m$:

$$[0,1,2,\dots,m-1,\underbrace{m,m,\dots,m}_{n-m\text{ copies}}]$$

So we get the same clean form immediately, with $p=m$.

If $p\ge n-1$, this is just the permutation $0,1,\dots,n-1$, whose MEX behavior is fixed forever. The answer is:

$$\frac{n(n-1)}2$$

The Period-2 Cycle

For $p\le n-2$, the clean low state is:

$$0,1,\dots,p-1 \text{ once each, and } p \text{ repeated } n-p \text{ times}$$

Its MEX is $p+1$, because $0$ through $p$ are present.

Apply the operation:

• $0,1,\dots,p-1$ stay, because they are unique below the MEX
• the copies of $p$ do not stay, because $p$ is duplicated
• all those copies become $p+1$

So it becomes the high state:

$$0,1,\dots,p-1 \text{ once each, and } p+1 \text{ repeated } n-p \text{ times}$$

Now the MEX is $p$, because $p$ is missing. Apply the operation again, and all the $p+1$ values become $p$. Back to the low state.

So after reaching the clean form, the array alternates forever. Very considerate of it, honestly.

The low-state sum is:

$$L = \frac{p(p-1)}2 + p(n-p)$$

The high-state sum is:

$$H = \frac{p(p-1)}2 + (p+1)(n-p)$$

Putting It Together

Compute the initial MEX $m$ and the first duplicated value below it.

• If $k=1$, output the direct one-operation sum.
• If no duplicated value exists below $m$:
  • use $p=m$
  • the clean low state starts after operation $1$
  • if $p\ge n-1$, output $\frac{n(n-1)}2$
  • otherwise use parity of $k-1$
• If a duplicated value exists:
  • use that first duplicate as $p$
  • the clean low state starts after operation $2$
  • use parity of $k-2$

The runtime is $O(n)$ per test case, and the total $n$ is bounded, so this cruises comfortably.