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:
import sys
from itertools import combinations

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class BitSum:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    def ng():
        px=-1
        for i in range(n):
            if i % 2:
                x = xx1[i // 2][1]
            else:
                x = xx0[i // 2][0]
            if x<px:return True
            px=x
        return False

    def change(ans):
        res=0
        bit=BitSum(n)
        for i,k in enumerate(kk):
            res+=i-bit.sum(k)
            if res>ans:return ans
            bit.add(k,1)
        return res

    n = II()
    aa = LI()
    bb = LI()
    ab = []
    for i, (a, b) in enumerate(zip(aa, bb)):
        if i % 2:
            ab.append([b, a, i])
        else:
            ab.append([a, b, i])
    ans=1000
    for odd in combinations(range(n), n // 2):
        isodd = [False] * n
        xx0 = []
        xx1 = []
        for i in odd:
            xx1.append(ab[i])
            isodd[i] = True
        for i in range(n):
            if isodd[i]: continue
            xx0.append(ab[i])
        xx0.sort(key=lambda x: (x[0],x[2]))
        xx1.sort(key=lambda x: (x[1],x[2]))
        #print(xx0)
        #print(xx1)
        if ng():continue
        kk=[]
        for [_,_,i0],[_,_,i1] in zip(xx0,xx1):
            kk+=[i0,i1]
        if n%2:kk+=[xx0[-1][2]]
        #print(kk)
        ans=change(ans)
        #print(ans,xx0,xx1)
    if ans==1000:print(-1)
    else:print(ans)

main()