Sum Minimisation

The problem looks like it wants simulation. It absolutely does not. The whole thing collapses to checking two states:

1. the current array;
2. the array after decreasing one smallest element by $1$.

If either one is a terminal state, we know the finite answer. Otherwise the sum can go to $-\infty$, so print -1.

When Is An Array Terminal?

Call an array terminal if no operation can decrease the sum.

Take any chosen set $S$ of size $k$. Its sum is $x$, and the operation decreases the total sum by

$$y = x - \left\lfloor\frac{x}{k}\right\rfloor k = x \bmod k.$$

So the operation changes nothing exactly when $x$ is divisible by $k$.

Therefore an array is terminal iff:

every subset of size $k$ has sum divisible by $k$, for every $2\le k\le n$.

Now fix some $k<n$. Suppose every $k$-subset has sum divisible by $k$. Pick two indices $i,j$. Since $k<n$, we can choose the other $k-1$ elements the same way and compare two subsets:

$$T\cup\{i\},\qquad T\cup\{j\}.$$

Both sums are $0\pmod k$, so their difference is also $0\pmod k$:

$$a_i-a_j\equiv 0\pmod k.$$

So for every $2\le k<n$, all elements must be congruent modulo $k$.

For $k=n$, there is only one subset: the whole array. So we only need

$$\sum a_i \equiv 0\pmod n.$$

Thus the terminal condition is:

• for every $2\le k<n$, all $a_i$ have the same residue modulo $k$;
• the total sum is divisible by $n$.

That is the main number theory bit. Tiny, but mean.

The One-Step Case

Suppose the current array is not terminal, but after decreasing a smallest element by $1$, it becomes terminal.

Let that terminal array be $b$, and the current array be $a$, where only the smallest element differs:

$$a_m=b_m+1.$$

Now look at any chosen set $S$.

• If $m\notin S$, then its sum in $a$ equals its sum in $b$, so it is divisible by $|S|$. No decrease.
• If $m\in S$, then its sum in $a$ is exactly one more than in $b$, so the remainder is $1$.

Since $a_m$ is a globally smallest element, when the remainder is $1$, the operation decreases exactly that element. So every useful move sends us straight to the terminal array.

Answer: original sum minus $1$.

Why Everything Else Is Infinite

Now assume neither the original array nor the array after decreasing the smallest element by $1$ is terminal.

Then the array is not just "not done"; it is doomed. There is a way to keep decreasing forever.

The key parity trap is this:

If, after excluding the current smallest element, there are elements of both parities, then the current smallest can be decreased forever. When the smallest is even, pair it with an odd anchor. When it is odd, pair it with an even anchor. A pair with odd sum has remainder $1$, and the smaller element is the current minimum, so it gets decreased. Repeat. Free infinite descent, no fancy machinery.

If the remaining elements do not already contain both parities, then all of them have the same parity. Any legal operation performed completely among those remaining elements flips the parity of at least one of them and not all of them, which creates the parity trap. There is one annoying edge case where it only decreases another copy of the minimum; doing the analogous operation once more gives two lowered elements, and the trap appears anyway. This is the part where the operation's "decrease the smallest values" rule actually matters.

If no such operation exists among the remaining elements, then the only useful moves must involve the global minimum. If decreasing that minimum once made the whole array terminal, we would be in the one-step case above. But we assumed it does not. So either some move decreases the minimum together with another element, immediately creating the parity trap, or we can keep decreasing the minimum until such a move appears. If it never appears, the minimum is already going down forever. Either way, the sum is unbounded below.

So the classification is complete:

• terminal now: answer is $\sum a_i$;
• terminal after decreasing one smallest element: answer is $\sum a_i-1$;
• otherwise: answer is -1.

Checking Terminal Fast

For $n\le 23$, directly test all moduli $2,3,\dots,n-1$.

For $n\ge 24$, the condition forces all elements to be equal. Why? If all elements are congruent modulo every number from $2$ through $23$, then every difference is divisible by

$$\operatorname{lcm}(2,3,\dots,23)=5354228880>10^9.$$

But the values we check are between $0$ and $10^9$, so a nonzero difference cannot be that large in divisibility terms. Therefore every difference is $0$.

So for large $n$, terminal just means all values are equal, plus the sum divisibility check. The divisibility is automatic when all values are equal, but keeping the check makes the function uniform and harmless.

Complexity: sorting dominates, so $O(n\log n)$ per test case, with total $n\le 10^6$.