Problem: 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 ≤ n ≤ 4 ⋅ 10^5) — the number of marbles.

The second line contains an integer sequence a_1, a_2, ..., a_n (1 ≤ a_i ≤ 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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
long long power(long long a, long long b, long long p) {
  if (!b) return 1;
  long long t = power(a, b / 2, p);
  t = t * t % p;
  if (b & 1) t = t * a % p;
  return t;
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long px, py;
  long long d = exgcd(b, a % b, px, py);
  x = py;
  y = px - a / b * py;
  return d;
}
template <class T>
inline void freshmin(T &a, const T &b) {
  if (a > b) a = b;
}
template <class T>
inline void freshmax(T &a, const T &b) {
  if (a < b) a = b;
}
namespace io {
const int BUFSIZE = 1 << 20;
int isize, osize;
char ibuf[BUFSIZE + 10], obuf[BUFSIZE + 10];
char *is, *it, *os = obuf, *ot = obuf + BUFSIZE;
char getchar() {
  if (is == it) {
    is = ibuf;
    it = ibuf + fread(ibuf, 1, BUFSIZE, stdin);
    if (is == it) return EOF;
  }
  return *is++;
}
char getalpha() {
  char c = getchar();
  while (!isalpha(c)) c = getchar();
  return c;
}
void putchar(char c) {
  *os++ = c;
  if (os == ot) {
    fwrite(obuf, 1, BUFSIZE, stdout);
    os = obuf;
  }
}
int inp() {
  int x = 0, f = 0;
  char ch;
  for (ch = getchar(); !isdigit(ch); ch = getchar())
    if (ch == '-') f = 1;
  for (; isdigit(ch); x = x * 10 + ch - '0', ch = getchar())
    ;
  return f ? -x : x;
}
long long inp_ll() {
  long long x = 0;
  int f = 0;
  char ch;
  for (ch = getchar(); !isdigit(ch); ch = getchar())
    if (ch == '-') f = 1;
  for (; isdigit(ch); x = x * 10 + ch - '0', ch = getchar())
    ;
  return f ? -x : x;
}
template <class T>
bool read(T &x) {
  x = 0;
  char ch = getchar();
  if (ch == EOF) return 0;
  for (; !isdigit(ch);) {
    ch = getchar();
    if (ch == EOF) return 0;
  }
  for (; isdigit(ch); x = x * 10 + ch - '0', ch = getchar())
    ;
  return 1;
}
template <class T>
void write(T x) {
  static char s[22];
  static char *it = s + 20;
  static char *end = s + 20;
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  do {
    *--it = x % 10 + '0';
    x /= 10;
  } while (x);
  for (; it < end; ++it) putchar(*it);
}
template <>
void write(const char *s) {
  for (; *s; ++s) putchar(*s);
}
template <>
void write(char c) {
  putchar(c);
}
template <class T, class V>
void write(T x, V y) {
  write(x);
  write(y);
}
template <class T>
void writeln(T x) {
  write(x);
  putchar('\n');
}
struct ender {
  ~ender() {
    if (os != obuf) fwrite(obuf, 1, os - obuf, stdout);
  }
} __ender;
}  // namespace io
template <class T>
void print(const T &a) {
  for (auto x : a) printf("%d ", x);
  puts("");
}
const int MAXN = 400010;
const int MAXK = 17;
const i64 INF = 1000000000000000000LL;
const int MOD = 1000000007;
const int INV2 = (MOD + 1) / 2;
const int INV6 = power(6, MOD - 2, MOD);
using namespace io;
int n;
int a[MAXN];
vector<int> v[MAXN];
int calc(int x, int p) {
  return upper_bound(v[x].begin(), v[x].end(), p) - v[x].begin();
}
long long F[20][1 << 20];
long long G[1 << 20];
void solve() {
  n = inp();
  for (int i = 1; i <= n; ++i) {
    a[i] = inp() - 1;
    v[a[i]].push_back(i);
  }
  for (int x = 0; x < 20; ++x) {
    for (int y = 0; y < 20; ++y)
      if (x != y) {
        long long tmp = 0;
        for (auto p : v[y]) tmp += calc(x, p);
        F[y][1 << x] = tmp;
      }
  }
  for (int x = 0; x < 20; ++x) {
    for (int s = 1; s < 1 << 20; ++s) {
      int t = s & -s;
      F[x][s] = F[x][s ^ t] + F[x][t];
    }
  }
  for (int s = 1; s < 1 << 20; ++s) {
    G[s] = INF;
    for (int i = 0; i < 20; ++i)
      if (s >> i & 1)
        freshmin(G[s], G[s ^ (1 << i)] + F[i][((1 << 20) - 1) ^ s]);
  }
  cout << G[(1 << 20) - 1] << endl;
}
int main() {
  solve();
  return 0;
}