Zhily and Mex and Max

Observation 1: the global maximum should appear immediately

Let $M = \max(a), \qquad K = \operatorname{mex}(a)$ for the whole multiset.

Forget the exact order for a second. Look at the prefixes before the first $0$ appears. For all of them, $\operatorname{mex}=0.$ So in that entire initial segment, the contribution is just the prefix maximum.

That means two things:

• we want the maximum there to be as large as possible as early as possible, so putting one copy of $M$ first is optimal;
• once $M$ is already first, putting more elements before the first $0$ is useless: the prefix maximum is already $M$, the mex is still $0$, and we're just delaying the moment when mex can start growing.

So in some optimal permutation, a copy of $M$ is first, and then the first missing-needed value should come as soon as possible.

If $K=0$ (there is no $0$ in the whole array), then mex is always $0$ no matter what, so putting $M$ first makes every prefix maximum equal to $M$, and the answer is simply $nM.$ Done.

---

Observation 2: after $M$ is in the prefix, the max is already "solved"

Now assume $K>0$, so at least one $0$ exists.

Once the first element is $M$, every later prefix already has $\max = M.$ That part of the objective is finished. Cooked. Done. Stick a fork in it.

So from now on, the only real game is to make the mex increase as early as possible.

Suppose the current prefix already contains all values $0,1,2,\dots,x-1,$ but does not contain $x$. Then the current mex is exactly $x$.

Now compare two choices for the next element:

• place some $y\ne x$ next;
• place $x$ next.

If you place $y\ne x$, then:

• the maximum stays $M$;
• the mex stays $x$.

If you place $x$, then:

• the maximum still stays $M$;
• the mex becomes at least $x+1$.

So placing $x$ next is never worse, and is usually strictly better.

That gives a clean exchange argument:

After $M$ is already in the prefix, between the first appearance of $x-1$ and the first appearance of $x$, there should be nothing except $x$ itself.

Inductively, the useful part of the permutation is forced.

---

Canonical optimal order

An optimal permutation can be chosen as $[M,\ 0,1,2,\dots,K-1]$ where we skip one copy of $M$ inside that increasing part if the front element already used it.

Examples:

• for $[0,1,2]$, we get $[2,0,1]$;
• for $[1,1,1,1,0]$, we get $[1,0,\dots]$;
• for an array with no $0$, we just put $M$ first and the rest does not matter.

After all values $0,1,\dots,K-1$ have appeared, the mex is permanently $K,$ and the maximum is already permanently $M.$ So every remaining element is just filler, and each remaining prefix contributes exactly $M+K.$

This is the whole punchline:

the answer depends only on $M$, $K$, and $n$.

You do not need to sort the array or build the permutation explicitly.

---

How to compute the answer

We split the objective into two parts.

1. Sum of prefix maxima

Because we place $M$ first, every prefix maximum is $M$. So $\sum_{i=1}^{n} \max(a_1,\dots,a_i) = nM.$

2. Sum of prefix mex values

Simulate only the canonical useful prefix:

1. add one copy of $M$;
2. then add $0,1,2,\dots,K-1$, skipping $M$ if needed.

Maintain a boolean array seen for values $0..K$, and the current mex curMex. Each time you add one of those special elements, update curMex and add it to the mex sum.

Let the length of this special prefix be $L$. Then the remaining $n-L$ positions all contribute mex $K$, so add $(n-L)K.$

Finally, $\text{answer} = nM + \text{mexSum}.$

---

Why this is correct

The proof is just the two observations above glued together:

1. Before the first $0$, mex is always $0$, so we should put the global maximum first; any extra elements before the first $0$ are wasted.
2. After the global maximum is already present, the maximum can never improve anymore. So whenever the current mex is $x$, placing anything other than $x$ next is pointless, because it leaves both state variables unchanged for one more prefix.
3. Therefore the first useful appearances must happen in the order $M,0,1,2,\dots,K-1$ (skipping one extra copy of $M$ if it was already used).
4. After that, the state is fixed forever at $\max=M,\ \operatorname{mex}=K,$ so the rest is filler.

That’s it. No DP, no black magic, no sacrificial goats.

---

Complexity

For each test case:

• computing $M$ is $O(n)$;
• computing $K$ (the mex of the whole array) is $O(n)$ using a presence array for values $0..n$;
• simulating the special prefix is $O(K) \subseteq O(n)$.

So the total complexity is $O(n)$ per test case, and $O\left(\sum n\right)$ over all test cases.

Memory usage is $O(n).$