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

Solution:
#include <bits/stdc++.h>
#define SIZE 20
#define BT (1<<19)
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int dp[BT][SIZE];
int A[SIZE],B[SIZE];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&A[i]);
	for(int i=0;i<n;i++) scanf("%d",&B[i]);
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<n;i++) dp[1<<i][i]=0;
	for(int S=1;S<(1<<n);S++)
	{
		int c=0;
		for(int i=0;i<n;i++) if(S>>i&1) c++;
		for(int i=0;i<n;i++)
		{
			if(!(S>>i&1)||dp[S][i]==-1) continue;
			//printf("%d %d : %d\n",S,i,dp[S][i]);
			int w=(i%2==c%2?B[i]:A[i]);
			int cost=c;
			for(int j=0;j<n;j++)
			{
				if(S>>j&1) cost--;
				else
				{
					int v=(j%2==c%2?A[j]:B[j]);
					if(w<=v)
					{
						int vl=dp[S][i]+cost;
						if(dp[S|1<<j][j]==-1||dp[S|1<<j][j]>vl) dp[S|1<<j][j]=vl;
					}
				}
			}
		}
	}
	int ret=-1;
	for(int i=0;i<n;i++)
	{
		if(dp[(1<<n)-1][i]!=-1)
		{
			//printf("%d %d\n",i,dp[(1<<n)-1][i]);
			if(ret==-1||ret>dp[(1<<n)-1][i]) ret=dp[(1<<n)-1][i];
		}
	}
	printf("%d\n",ret);
	return 0;
}