Snowfall

Observation 1: reduce everything to divisibility by $2$ and $3$

A subarray product is divisible by $6$ iff its product has both a factor $2$ and a factor $3$.

So every number belongs to exactly one of these four types:

• $A$: divisible by $6$
• $B$: divisible by $2$ but not by $3$
• $C$: divisible by $3$ but not by $2$
• $D$: divisible by neither $2$ nor $3$

From now on, the actual values are irrelevant. Only the type matters. Competitive programming in a nutshell: kill the fluff, keep the invariant.

---

Observation 2: first solve the case with no $A$-elements

Suppose the array contains only $B$, $C$, and $D$.

Then a subarray is good iff it contains:

• at least one $B$, and
• at least one $C$.

The $D$'s are just innocent bystanders.

Lower bound

Let there be $b$ elements of type $B$ and $c$ elements of type $C$.

Take any position of a $B$ and any position of a $C$. The interval between those two positions is a good subarray.

Different pairs of positions give different intervals, so every arrangement has at least

$bc$

good subarrays.

Can we achieve $bc$?

Yes. Arrange them as

$[B][D][C]$

(or symmetrically $[C][D][B]$).

Now every good subarray must start in the $B$ block and end in the $C$ block. So the number of good subarrays is exactly

$b \cdot c.$

That matches the lower bound, so this is optimal.

So, without any multiples of $6$, the optimal arrangement is:

$[B][D][C] \quad \text{or} \quad [C][D][B].$

---

Observation 3: what do the $A$-elements do?

Any subarray containing an element of type $A$ is automatically good. Those elements are basically landmines.

So to minimize $f(a)$, we want to maximize the number of subarrays that avoid all $A$'s.

If we delete all $A$'s, the remaining elements split into some segments. Let these segments have lengths

$m_1, m_2, \dots, m_k.$

Then the number of subarrays avoiding all $A$'s is

$\sum_{i=1}^k \frac{m_i(m_i+1)}{2}.$

This is maximized when there is only one such segment, because

$\frac{(x+y)(x+y+1)}{2} \ge \frac{x(x+1)}{2} + \frac{y(y+1)}{2}.$

So the non-$A$ elements should form one contiguous block. Equivalently, all $A$'s should be pushed to an edge (or split between the two edges — same idea, but one edge is simpler).

---

Observation 4: combining both parts

Let:

• $a = |A|$
• $b = |B|$
• $c = |C|$
• $d = |D|$
• $m = b+c+d$

If all non-$A$ elements form one block, then:

• every subarray touching the $A$-block is good,
• inside the non-$A$ block, the minimum possible number of good subarrays is $bc$, achieved by $[B][D][C]$.

So an optimal arrangement is simply

$[A][B][D][C]$

or the reverse

$[C][D][B][A].$

That’s it. No DP, no black magic, no goat sacrifice.

---

Why this is globally optimal

Let the $A$-free segments be $s_1, s_2, \dots, s_k$. For segment $i$, let:

• length be $m_i$,
• number of $B$'s be $b_i$,
• number of $C$'s be $c_i$.

Then:

1. Subarrays containing at least one $A$ contribute $\frac{n(n+1)}{2} - \sum_i \frac{m_i(m_i+1)}{2}.$

2. Inside segment $i$, by the same pair argument as before, there are at least $b_i c_i$ good subarrays.

Therefore

$$f(a) \ge \frac{n(n+1)}{2} - \sum_i \frac{m_i(m_i+1)}{2} + \sum_i b_i c_i.$$

Now compare this with the one-block arrangement. Since

$$\frac{m(m+1)}{2} - \sum_i \frac{m_i(m_i+1)}{2} = \sum_{i<j} m_i m_j,$$

and also

$$bc - \sum_i b_i c_i = \sum_{i<j}(b_i c_j + b_j c_i),$$

while clearly

$m_i m_j \ge b_i c_j + b_j c_i,$

we get

$$f(a) \ge \frac{n(n+1)}{2} - \frac{m(m+1)}{2} + bc.$$

And the construction $[A][B][D][C]$ achieves exactly this bound. So it is optimal.

---

Algorithm

For each test case:

1. Split all numbers into four vectors:
   • multiples of $6$,
   • multiples of $2$ only,
   • multiples of $3$ only,
   • neither.
2. Output them in the order $[A][B][D][C].$

That’s all.

---

Complexity

Each number is classified once, so the complexity is

$O(n)$

per test case, and

$O\left(\sum n\right)$

over the whole input.

Memory usage is also $O(n)$.

Pretty damn cheap for an optimal construction.