Marbles
Contest: Codeforces Round 585 (Div. 2)
Difficulty rating: 2200
Tags: bitmasks, dp

Monocarp has arranged $$$n$$$ colored marbles in a row. The color of the $$$i$$$-th marble is $$$a_i$$$. Monocarp likes ordered things, so he wants to rearrange marbles in such a way that all marbles of the same color form a contiguos segment (and there is only one such segment for each color).

In other words, Monocarp wants to rearrange marbles so that, for every color $$$j$$$, if the leftmost marble of color $$$j$$$ is $$$l$$$-th in the row, and the rightmost marble of this color has position $$$r$$$ in the row, then every marble from $$$l$$$ to $$$r$$$ has color $$$j$$$.

To achieve his goal, Monocarp can do the following operation any number of times: choose two neighbouring marbles, and swap them.

You have to calculate the minimum number of operations Monocarp has to perform to rearrange the marbles. Note that the order of segments of marbles having equal color does not matter, it is only required that, for every color, all the marbles of this color form exactly one contiguous segment.

Input format:
The first line contains one integer $$$n$$$ $$$(2 \le n \le 4 \cdot 10^5)$$$ — the number of marbles.

The second line contains an integer sequence $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 20)$$$, where $$$a_i$$$ is the color of the $$$i$$$-th marble.

Output format:
Print the minimum number of operations Monocarp has to perform to achieve his goal.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first example three operations are enough. Firstly, Monocarp should swap the third and the fourth marbles, so the sequence of colors is $$$[3, 4, 3, 2, 4, 2, 2]$$$. Then Monocarp should swap the second and the third marbles, so the sequence is $$$[3, 3, 4, 2, 4, 2, 2]$$$. And finally, Monocarp should swap the fourth and the fifth marbles, so the sequence is $$$[3, 3, 4, 4, 2, 2, 2]$$$.

In the second example there's no need to perform any operations.

Example input:
7
3 4 2 3 4 2 2

Example output:
3

Example input:
5
20 1 14 10 2

Example output:
0

Editorial:
The main fact is that the number of colors is less than $$$20$$$, which allows us to use exponential solutions.
For each pair of colors $$$(i, j)$$$, we can calculate $$$cnt[i][j]$$$ — the number of swaps required to place all marbles of color $$$i$$$ before all marbles of color $$$j$$$ (if we consider only marbles of these two colors). We can store a sorted vector for each color, and calculate this information for a fixed pair with two pointers.
Then let's use subset DP to fix the order of colors. Let $$$d[mask]$$$ be the minimum number of operations to correctly order all marbles from the $$$mask$$$ of colors. Let's iterate on the next color we consider — it should be a position in binary representation of $$$mask$$$ with $$$0$$$ in it. We will place all marbles of this color after all marbles we already placed. If we fix a new color $$$i$$$, let's calculate the $$$sum$$$ (the additional number of swaps we have to make) by iterating on the bit $$$j$$$ equal to $$$1$$$ in the $$$mask$$$, and increasing $$$sum$$$ by $$$cnt[j][i]$$$ for every such bit. The new state of DP can be calculated as $$$nmask = mask | (1 « i)$$$. So the transition can be implemented as $$$d[nmask] = min(d[nmask], d[mask] + sum)$$$.
The answer is the minimum number of swaps required to place all the colors, and that is $$$d[2^{20} - 1]$$$.