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 JAVA):

Solution:
import java.io.*;
import java.util.*;

import static jdk.nashorn.internal.objects.Global.print;

/**
 * A simple template for competitive programming problems.
 */
public class Banana {
    final InputReader in = new InputReader(System.in);
    final PrintWriter out = new PrintWriter(System.out);

    boolean DEBUG = false;
    void solve() {
        int n = in.nextInt();
        int[] arr = in.nextArray(n);
        Set<Integer> hs = new HashSet<>();


        for(int i : arr)
            hs.add(i);

        int k = hs.size();

        int c = 0;
        Map<Integer, Integer> hm = new HashMap<>();
        for(int e : hs) {
            if(!hm.containsKey(e)){
                hm.put(e, c);
                c++;
            }
        }

        for(int i=0; i<n; i++) {
            arr[i] = hm.get(arr[i]);
        }

        if(DEBUG) {
            System.out.println("arr: ");
            printArray(arr);
            System.out.println();
        }

        long[] sums = new long[k];

        for(int i=0; i<n; i++) {
            sums[arr[i]] += i;
        }

        long[][] w = new long[k][k];

        long[] count = new long[k];

        for(int i=0; i<n; i++) {
            for(int j=0; j<k; j++) {
                w[arr[i]][j] += count[j];
            }
            count[arr[i]]++;
        }

        if(DEBUG) {
            System.out.println("w");
            printMatrix(w);
            System.out.println();
        }

        long[] dp = new long[1<<k];

        for(int i=1; i<1<<k; i++) {
            long min = Long.MAX_VALUE;
            for(int j=0; j<k; j++) {
                if((i&(1<<j))>0) {
                    int bitWithout = i^(1<<j);
                    long val = dp[bitWithout]+sums[j];
                    for(int t=0; t<k; t++) {
                        if(((1<<t)&i)>0) {
                            val -= w[j][t];
                        }
                    }
                    min = Math.min(val, min);
                }
            }
            dp[i] = min;
        }

        out.println(dp[(1<<k) - 1]);
    }

    private void printMatrix(long[][] w) {
        for(int i=0; i<w.length; i++) {
            printArray(w[i]);
        }
    }

    private void printArray(long[] arr) {
        for(long i: arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    private void printArray(int[] arr) {
        for(int i: arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) throws FileNotFoundException { Banana s = new Banana(); s.solve(); s.out.close(); }

    public Banana() throws FileNotFoundException { }

    private static class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        InputReader(InputStream stream) {
            this.stream = stream;
        }

        InputReader(String fileName) {
            InputStream stream = null;
            try {
                stream = new FileInputStream(fileName);
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
            this.stream = stream;
        }

        int[] nextArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextInt();
            return arr;
        }

        int[] nextRandomArray(int n, int lim) {
            int[] arr = new int[n];
            Random r = new Random();
            for(int i=0; i<n; i++) {
                arr[i] = r.nextInt(lim);
            }
            return arr;
        }

        int[] nextRandomArray(int n) {
            int[] arr = new int[n];
            Random r = new Random();
            for(int i=0; i<n; i++) {
                arr[i] = r.nextInt();
            }
            return arr;
        }

        int[] nextRandomArray(int n, int low, int lim) {
            int[] arr = new int[n];
            Random r = new Random();
            for(int i=0; i<n; i++) {
                arr[i] = low+r.nextInt(lim-low+1);
            }
            return arr;
        }

        int[][] nextMatrix(int n, int m) {
            int[][] matrix = new int[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    matrix[i][j] = nextInt();
            return matrix;
        }

        String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        double nextDouble() {
            return Double.parseDouble(nextString());
        }

        private int read() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try { numChars = stream.read(buf); }
                catch (IOException e) { throw new InputMismatchException(); }
                if (numChars <= 0) return -1;
            }
            return buf[curChar++];
        }

        private boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; }

        private boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; }
    }


}