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.io.*;
import java.util.*;

public class Main {
    static long mod = (int)Math.pow(10,9)+7;
    static int n, max = 100000000 , a[][], memo[][];
	public static void main(String[] args) throws IOException {
		FastScanner sc = new FastScanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		n = sc.nextInt();
		a = new int[n][2];
		memo = new int[51][1 << n];
		for (int[] x : memo){
		    Arrays.fill(x, -1);
		}
		for (int j = 0; j < 2; j++){
		    for (int i = 0; i < n; i++){
		        a[i][j] = sc.nextInt();
		    }
		}
		int ans = dp(0,0,0);
		pw.println(ans >= max ? -1 : ans);
		pw.close();
	}
	    /*
	        msk = 既に使用したかどうかの判定
	        memo[last][msk] = mskのbitを使用した状態で一番最後の数字がlastになる最小の転倒数
	        last <= valの未使用bitが存在する場合、dp(使用した値のbit+msk,idx++,val)を呼び出す(そうでない場合はそのままreturn)
	        newPosは値の位置 + i < jであるものの内、既に使用されている(mskに追加されている)値の数
	        
	    */
		static int dp(int msk, int idx, int last) {
		if (idx == n)
			return 0;
		if (memo[last][msk] != -1)
			return memo[last][msk];
		int ans = max;
		for (int put = 0; put < n; put++) {
			if ((msk & 1 << put) != 0){ 
			    continue;
			}
			int all = (1 << (put + 1)) - 1; //これまで適用したビット
			int newPos = put + Integer.bitCount(msk&~all);
			int val = a[put][Math.abs(put - idx) % 2]; //Math.abs(put - idx) % 2 == 0 ? 表 : 裏
			//System.out.println(idx+" "+last+" "+msk+" "+ put+" "+all+" "+newPos+" "+val + " " + Integer.bitCount(msk&~all));
			if (val >= last) {
				ans = Math.min(ans, dp(msk | 1 << put, idx + 1, val) + Math.abs(newPos - idx));
			}
		}
		return memo[last][msk] = ans;
 
	}
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;
    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
         return Double.parseDouble(next());
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    } 
}