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.ArrayList;
import java.util.Comparator;
import java.util.Scanner;



public class Main {


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		Card[] cards = new Card[n];
		for (int i=0;i<n;i++) {
			cards[i]=new Card();
			cards[i].id=i+1;
		}
		for (int i=0;i<n;i++) {
			cards[i].red=sc.nextInt();
		}
		for (int i=0;i<n;i++) {
			cards[i].blue=sc.nextInt();
		}
		
		int ans = -1;
		
		for (int i=0;i<(1<<n);i++) {
			ArrayList<Card> odd = new ArrayList<>();
			ArrayList<Card> even = new ArrayList<>();
			for (int j=0;j<n;j++) {
				cards[j].showing=((i>>j)%2!=0 ? cards[j].blue : cards[j].red);
				if ((i>>j)%2!=0 ^ j%2==0) {
					odd.add(cards[j]);
				} else {
					even.add(cards[j]);
				}
			}
			if (odd.size() != (n+1)/2) {
				continue;
			}
			odd.sort(Comparator.comparing((Card c) -> c.showing).thenComparing((Card c) -> c.id));
			even.sort(Comparator.comparing((Card c) -> c.showing).thenComparing((Card c) -> c.id));
			
			int last = 0;
			ArrayList<Card> combined = combine(odd,even,n);
			boolean ok = true;
			for (int j=0;j<n-1;j++) {
				if(combined.get(j).showing>combined.get(j+1).showing){
					ok=false;
					break;
				}
			}
			
			if (ok) {
				int count = 0;
				for (int j=0;j<n;j++) {
					for (int k=j+1;k<n;k++) {
						if(combined.get(j).id>combined.get(k).id) {
							count++;
						}
					}
				}
				if (ans==-1 || count<ans) {
					ans=count;
				}
			}
		}
		
		System.out.println(ans);
	}
	static ArrayList<Card> combine (ArrayList<Card> odd, ArrayList<Card>even, int n) {
		ArrayList<Card> ret = new ArrayList<>();
		for (int i=0;i<n;i++) {
			ret.add(i%2==0 ? odd.get(i/2) : even.get(i/2));
		}
		return ret;
	}
}

class Card {
	int id;
	int red;
	int blue;
	int showing;
}