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

Solution:
from collections import deque

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

ans=float("inf")
count=0
def dfs(num,ro,re,bo,be):
    global ans,count
    count+=1
    if num==N:
        que=[]
        ro.sort(reverse=True)
        re.sort(reverse=True)
        bo.sort(reverse=True)
        be.sort(reverse=True)
        ropos=-1
        repos=-1
        bopos=-1
        bepos=-1
        for i in range(N):
            if i%2==0:
                if repos>=-len(re) and bopos>=-len(bo):
                    val1,num1=re[repos]
                    val2,num2=bo[bopos]
                    if val1>val2:
                        que.append([val2,num2])
                        bopos-=1
                    elif val2>val1:
                        que.append([val1,num1])
                        repos-=1
                    elif num1>num2:
                        que.append([val2,num2])
                        bopos-=1
                    else:
                        que.append([val1,num1])
                        repos-=1
                elif repos>=-len(re):
                    val,num=re[repos]
                    que.append([val,num])
                    repos-=1
                elif bopos>=-len(bo):
                    val,num=bo[bopos]
                    que.append([val,num])
                    bopos-=1
                else:
                    return 0
            else:
                if ropos>=-len(ro) and bepos>=-len(be):
                    val1,num1=ro[ropos]
                    val2,num2=be[bepos]
                    if val1>val2:
                        que.append([val2,num2])
                        bepos-=1
                    elif val2>val1:
                        que.append([val1,num1])
                        ropos-=1
                    elif num1>num2:
                        que.append([val2,num2])
                        bepos-=1
                    else:
                        que.append([val1,num1])
                        ropos-=1
                elif ropos>=-len(ro):
                    val,num=ro[ropos]
                    que.append([val,num])
                    ropos-=1
                elif bepos>=-len(be):
                    val,num=be[bepos]
                    que.append([val,num])
                    bepos-=1
                else:
                    return 0


        for i in range(1,N):
            if que[i][0]<que[i-1][0]:
                return 0

        temp=0
        for i in range(1,N):
            for j in range(0,i):
                if que[i][1]<que[j][1]:
                    temp+=1
        ans=min(ans,temp)
        return 0

    if num%2==0:
        dfs(num+1,ro,re+[[A[num],num]],bo,be)
        dfs(num+1,ro,re,bo,be+[[B[num],num]])
    else:
        dfs(num+1,ro+[[A[num],num]],re,bo,be)
        dfs(num+1,ro,re,bo+[[B[num],num]],be)

dfs(0,[],[],[],[])
print(ans if ans!=float("inf") else -1)