Problem: We have N cards numbered 1, 2, ..., N. Card i (1 \leq i \leq N) has an integer A_i written in red ink on one side and an integer B_i written in blue ink on the other side. Initially, these cards are arranged from left to right in the order from Card 1 to Card N, with the red numbers facing up.

Determine whether it is possible to have a non-decreasing sequence facing up from left to right (that is, for each i (1 \leq i \leq N - 1), the integer facing up on the (i+1)-th card from the left is not less than the integer facing up on the i-th card from the left) by repeating the operation below. If the answer is yes, find the minimum number of operations required to achieve it.

* Choose an integer i (1 \leq i \leq N - 1). Swap the i-th and (i+1)-th cards from the left, then flip these two cards.

Constraints

* 1 \leq N \leq 18
* 1 \leq A_i, B_i \leq 50 (1 \leq i \leq N)
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N
B_1 B_2 ... B_N


Output

If it is impossible to have a non-decreasing sequence, print `-1`. If it is possible, print the minimum number of operations required to achieve it.

Examples

Input

3
3 4 3
3 2 3


Output

1


Input

2
2 1
1 2


Output

-1


Input

4
1 2 3 4
5 6 7 8


Output

0


Input

5
28 15 22 43 31
20 22 43 33 32


Output

-1


Input

5
4 46 6 38 43
33 15 18 27 37


Output

3

Solution (in JAVA):

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

public class Main {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out,false);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        int[] barr = new int[n];
        for(int i = 0; i < n; i++) {
            barr[i] =scanner.nextInt();
        }
        int sz = 51;
        int maxMask = 1 << n;
        int[][] dp = new int[maxMask][sz];
        for(int[] dd: dp) Arrays.fill(dd, Integer.MAX_VALUE/3);
        int[][] swapVals = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j< n; j++) {
                swapVals[i][j] = (i % 2 == j % 2) ? arr[j] : barr[j];
            }
        }
        dp[0][0] = 0;
        for(int mask = 0; mask < maxMask; mask++) {
            //position corresponds the number of bits that are highlighted in the mask
            int ind = Integer.bitCount(mask);
            for(int val = 0; val < sz; val++) {
                int cost = 0;
                for(int i = 0;i < n; i++) {
                    if(((1 << i) & mask) > 0) continue;
                    //which face is the card that i can put here?
                    //and is it greater than my prev?
                    if (swapVals[ind][i] >= val) dp[mask | (1 << i)][swapVals[ind][i]] = Math.min(dp[mask][val] + cost, dp[mask|(1<<i)][swapVals[ind][i]]);
                    cost++;
                }
            }
        }
        int ans = Integer.MAX_VALUE/3;
        maxMask--;
        for(int i = 0; i < sz; i++) {
            ans= Math.min(ans, dp[maxMask][i]);
        }
        out.println(ans == Integer.MAX_VALUE/3 ? -1 : ans);
        out.flush();
    }
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}