Equal Occurrences

A balanced subsequence means all values that appear in it appear the same number of times.

So the subsequence has a hidden parameter: the common count. Call it $k$.

If we choose values $x_1, x_2, \dots, x_m$, then the subsequence length is:

$$k \cdot m$$

because each chosen value appears exactly $k$ times.

Counting Frequencies

Since $a_i \le n$, we can count how many times each value appears. Let $freq[v]$ be the number of occurrences of value $v$ in the original array.

For a value $v$ to be usable with common count $k$, we need:

$$freq[v] \ge k$$

because we can delete extra copies, but we cannot invent missing ones. Shocking, I know.

Fixed $k$

Suppose we decide every chosen value must appear exactly $k$ times.

Then every value with $freq[v] \ge k$ can be included. Including it adds exactly $k$ elements and does not break balance. So for this fixed $k$, the best choice is to include all such values.

If there are $cnt$ values with frequency at least $k$, the best balanced subsequence length for this $k$ is:

$$k \cdot cnt$$

Trying All Possibilities

The common count $k$ cannot be more than $n$, so we just try all $k$ from $1$ to $n$.

For each $k$:

1. Count how many values have frequency at least $k$.
2. Update the answer with $k \cdot cnt$.

This covers every possible balanced subsequence because every balanced subsequence has some common occurrence count $k$.

Why This Is Correct

Take any optimal balanced subsequence. Suppose each chosen value appears exactly $k$ times in it. Then every chosen value must have appeared at least $k$ times in the original array.

Our algorithm, when checking this same $k$, includes every value with frequency at least $k$, including all values from that optimal subsequence and possibly more. Therefore, our candidate length for this $k$ is at least as large as that optimal subsequence.

Since we try every $k$, we cannot miss the optimum.

Complexity

There are at most $n$ possible values and $n$ possible values of $k$, so the solution is $O(n^2)$ per test case. With $n \le 100$, this is tiny. The CPU barely gets out of bed.