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 defaultdict
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += i-bit.sum(p)
        bit.add(p, 1)
    return ans
N = int(input())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
us = []
vs = []
for i in range(N):
    a, b = xs[i], ys[i]
    if i%2:
        us.append((a,i))
        vs.append((b,i))
    else:
        us.append((b,i))
        vs.append((a,i))
vs.sort()
r = 10**18
for i in range(2**N):
    t = 0
    tt = 0
    rs = [0]*N
    rs2 = [0]*(N//2)
    for j in range(N):
        if i%2:
            if 2*t < N:
                rs[t*2] = vs[j]
            t += 1
        else:
            if 2*tt+1 < N:
                rs2[tt] = us[vs[j][1]]
            tt += 1
        i = i>>1
    if t != (N+1)//2:
        continue
    rs2.sort()
    for i in range(N//2):
        rs[i*2+1] = rs2[i]
    b,ff = 0,0
    for z,j in rs:
        if b>z:
            ff = 1
            break
        b = z
    if ff:
        continue
#    print(rs)
    rs = [j+1 for _,j in rs]
    r = min(r, tento(rs))
print(r if r != 10**18 else -1)