Arrange the Numbers in a Circle

Key Observation

Call a color heavy if we use it at least twice, and single if we use it exactly once.

A single color is very constrained. Suppose the single card is $y$, and its neighbors are $a$ and $b$. The triple $(a,y,b)$ must contain two equal values. Since $y$ appears only once, we must have:

$$a=b.$$

So every singleton has to be inserted between two equal cards, like $x,y,x$. The circle is not being cute here; it is forcing structure.

Heavy Colors Alone

If we use only heavy colors, we can arrange them in blocks:

$$1,1,\dots,1,\;2,2,\dots,2,\;3,3,\dots,3,\dots$$

Every block has length at least $2$, so any triple crossing a boundary still contains two equal cards. Therefore all chosen heavy colors can use all their available cards.

How Many Singletons Can We Insert?

Now suppose we have chosen some heavy colors.

Case 1: exactly one heavy color

If the heavy color has $c$ copies, place them in a circle. A singleton can be inserted into a gap between two equal copies.

But two inserted singleton gaps cannot be adjacent, because that would create:

$$y_1, x, y_2$$

with all three values distinct. So the maximum number of singleton insertions is:

$$\left\lfloor \frac{c}{2} \right\rfloor.$$

Case 2: at least two heavy colors

Now each heavy color block has other colors on both sides. If we insert a singleton too close to the edge of a block, we create a bad triple involving the neighboring block.

For a block of $c$ equal cards, usable insertion gaps are internal and non-adjacent. The maximum is:

$$\max\left(0, \left\lfloor \frac{c-2}{2} \right\rfloor\right).$$

So for several heavy colors, the total number of singleton slots is:

$$\sum \max\left(0, \left\lfloor \frac{c_i-2}{2} \right\rfloor\right).$$

Choosing the Heavy Colors

For a fixed number of heavy colors, we should choose the largest counts. Bigger $c_i$ gives more cards and never gives fewer singleton slots. Since the input is sorted, the heavy colors are some suffix.

Suppose the suffix starts at index $i$ in $0$-based indexing. Then:

$$\text{base} = \sum_{j=i}^{n-1} c_j.$$

There are $i$ remaining colors outside the suffix, and each can contribute at most one singleton card. If the chosen suffix has $\text{slots}$ singleton positions, we can add:

$$\min(i, \text{slots})$$

cards.

So the candidate answer is:

$$\text{base} + \min(i, \text{slots}).$$

Try every valid suffix whose first count is at least $2$.

Finally, if the best value is less than $3$, output $0$, because we must choose at least three cards.

Complexity

We scan the array once from right to left, maintaining suffix sums and slot counts.

$$O(n)$$

per test case, and

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

over the whole input. Memory is $O(n)$, mostly because we store the counts.