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-----

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-----

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


-----Examples-----
Input
7
3 4 2 3 4 2 2

Output
3

Input
5
20 1 14 10 2

Output
0

Input
13
5 5 4 4 3 5 7 6 5 4 4 6 5

Output
21



-----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.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Bit manipulation


Solutions:
n = int(input())
a = [int(x) for x in input().split()]
d = {}
for i in range(1, 21):
	for j in range(1, 21):
		d[i, j] = 0
cv = [0 for i in range(21)]
for j in a:
	for i in range(1, 21):
		d[i, j] += cv[i]
	cv[j] += 1
s = 0
for i in range(1, 21):
	for j in range(i + 1, 21):
		s += min(d[i, j], d[j, i])
print(s)


import sys
n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split()))
M = [[0 for i in range(0, 21)] for j in range(0, 21)]
F = [0 for i in range(0, 21)]
for i in range(0, n):
	x = int(a[i])
	for j in range(0, 21):
		if j != x:
			M[j][x] = M[j][x] + F[j]
	F[x] = F[x] + 1
ans = 0
for i in range(0, 21):
	for j in range(0, i):
		ans = ans + min(M[i][j], M[j][i])
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from collections import deque
for _ in range(int(input()) if not True else 1):
	n = int(input())
	a = list(map(int, input().split()))
	indexes = [[] for i in range(21)]
	for i in range(n):
		indexes[a[i]] += [i]
	pos = True
	for i in range(1, 21):
		if indexes[i]:
			if indexes[i] != list(range(indexes[i][0], indexes[i][0] + len(indexes[i]))):
				pos = False
				break
	if pos:
		print(0)
		continue
	n = 0
	for i in range(1, 21):
		if indexes[i]:
			indexes[n] = list(indexes[i])
			n += 1
			for x in indexes[n - 1]:
				a[x] = n
	moves = [[0] * n for i in range(n)]
	count = [0.0] * (n + 1)
	for i in range(len(a)):
		for j in range(1, n + 1):
			moves[a[i] - 1][j - 1] += count[j]
		count[a[i]] += 1
	dp = [float('inf')] * (1 << n)
	dp[0] = 0
	for mask in range(1 << n):
		unsetbits = [i for i in range(n) if not mask & 1 << i]
		for i in unsetbits:
			res = mask | 1 << i
			total = sum((moves[i][j] for j in unsetbits)) - moves[i][i]
			dp[res] = min(dp[res], dp[mask] + total)
	print(int(dp[-1]))