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.PrintWriter;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] a=new int[n];
		for(int i=0; i<n; i++){
			a[i]=sc.nextInt();
		}
		int[] b=new int[n];
		for(int i=0; i<n; i++){
			b[i]=sc.nextInt();
		}
		int ans=Integer.MAX_VALUE;
		for(int i=0; i<1<<n; i++){
			ArrayList<State> even=new ArrayList<>();
			ArrayList<State> odd=new ArrayList<>();
			for(int j=0; j<n; j++){
				if((i>>j & 1)==1){
					if(j%2==0){
						odd.add(new State(b[j],j));
					}else{
						even.add(new State(b[j],j));
					}
				}else{
					if(j%2==0){
						even.add(new State(a[j],j));
					}else{
						odd.add(new State(a[j],j));
					}
				}
			}
			if(n%2==0){
				if(even.size()!=odd.size()){
					continue;
				}
			}else{
				if(even.size()!=odd.size()+1){
					continue;
				}
			}
			Collections.sort(odd,(x,y)->(x.num-y.num));
			Collections.sort(even,(x,y)->(x.num-y.num));
			ArrayList<State> tmp=new ArrayList<>();
			for(int k=0; k<n/2; k++){
				tmp.add(even.get(k));
				tmp.add(odd.get(k));
			}
			if(even.size()>odd.size()){
				tmp.add(even.get(n/2));
			}
			if(!check(tmp)){
				continue;
			}
			ArrayList<Integer> index=new ArrayList<>();
			for(State s:tmp){
				index.add(s.index);
			}
			ans=Math.min(ans,bubble(index));
		}
		if(ans==Integer.MAX_VALUE){
			System.out.println(-1);
		}else{
			System.out.println(ans);
		}
	}
	static class State{
		int num,index;
		State(int num,int index){
			this.num=num;
			this.index=index;
		}
	}
	static int bubble(ArrayList<Integer> list){
		int count=0;
		for(int i=0; i<list.size(); i++){
			for(int j=list.size()-2; j>=0; j--){
				if(list.get(j)>list.get(j+1)){
					count++;
					Collections.swap(list,j,j+1);
				}
			}
		}
		return count;
	}
	static boolean check(ArrayList<State> list){
		for(int i=0; i<list.size()-1; i++){
			if(list.get(i).num>list.get(i+1).num){
				return false;
			}
		}
		return true;
	}
}