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:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

n =int(input())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]

L = range(n)
from itertools import combinations

ans = INF = 1000000
for I in combinations(L,n//2): #偶数番目を決め打ち全探索
    even = [(a[i] if i%2 else b[i], i) for i in I]
    odd  = [(b[i] if i%2 else a[i], i) for i in range(n) if i not in I]
    
    odd.sort()
    even.sort()
    ok = 1
    #偶数番目と奇数番目をマージしたとき、ソートされているか確認
    for i in range(n//2):
        if odd[i][0] > even[i][0]:
            ok = 0
            break
    for i in range(1,n-n//2):
        if even[i-1][0] > odd[i][0]:
            ok = 0
            break
    
    if ok:
        res = [0]*n
        for i in range(n//2):
            res[2*i+1] = even[i][1]
        for i in range(n-n//2):
            res[2*i] = odd[i][1]
        
        #転倒数の計算
        cnt = 0        
        for i in range(n):
            for j in range(i+1,n):
                if res[i] > res[j]: cnt += 1
        ans = min(ans,cnt)


if ans == INF: print(-1)
else: print(ans)