Problem:


Score : 700 points

Problem Statement

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.

Sample Input 1

3
3 4 3
3 2 3

Sample Output 1

1

By doing the operation once with i = 1, we have a sequence [2, 3, 3] facing up, which is non-decreasing.

Sample Input 2

2
2 1
1 2

Sample Output 2

-1

After any number of operations, we have the sequence [2, 1] facing up, which is not non-decreasing.

Sample Input 3

4
1 2 3 4
5 6 7 8

Sample Output 3

0

No operation may be required.

Sample Input 4

5
28 15 22 43 31
20 22 43 33 32

Sample Output 4

-1

Sample Input 5

5
4 46 6 38 43
33 15 18 27 37

Sample Output 5

3



Sample input:
3
3 4 3
3 2 3


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

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

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


from operator import itemgetter
from collections import deque

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 10**18

for bit_state in range(1 << n):
    pattern = [deque([]) for i in range(2)]
    for i in range(n):
        if bit_state & (1 << i) and i % 2 == 0:
            pattern[0].append((a[i], i))
        elif bit_state & (1 << i) and i % 2 == 1:
            pattern[1].append((a[i], i))
        elif i % 2 == 0:
            pattern[1].append((b[i], i))
        else:
            pattern[0].append((b[i], i))
     
    for i in range(2):
        pattern[i] = sorted(pattern[i], key = itemgetter(1))
        pattern[i] = sorted(pattern[i])

    if len(pattern[0]) == len(pattern[1]) or len(pattern[0]) - 1 == len(pattern[1]):
        bit = BIT(n)
        ans_tmp = 0
        prev_num = 10**8
        for i in range(n)[::-1]:
            pal = i % 2
            num, ind = pattern[pal].pop()
            if prev_num < num:
                break
            prev_num = num
            bit.add(ind, 1)
            ans_tmp += bit.get_sum(0, ind)
        else:
            ans = min(ans, ans_tmp)

if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

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

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


from operator import itemgetter

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 10**18

for bit_state in range(1 << n):
    tmp = [0] * n
    pos_even_palok = set()
    pos_odd_palok = set()
    pos_even_palng = set()
    pos_odd_palng = set()
    pattern = [[] for i in range(2)]

    for i in range(n):
        if bit_state & (1 << i) and i % 2 == 0:
            pattern[0].append((a[i], i))
            tmp[i] = 0
        elif bit_state & (1 << i) and i % 2 == 1:
            pattern[1].append((a[i], i))
            tmp[i] = 1
        elif i % 2 == 0:
            pattern[1].append((b[i], i))
            tmp[i] = 1
        else:
            pattern[0].append((b[i], i))
            tmp[i] = 0
     
    for i in range(2):
        pattern[i] = sorted(pattern[i], key = itemgetter(1))
        pattern[i] = sorted(pattern[i])
    if len(pattern[0]) == len(pattern[1]) or len(pattern[0]) - 1 == len(pattern[1]):
        bit = BIT(n)
        ans_tmp = 0
        prev_num = 10**8
        for i in range(n)[::-1]:
            pal = i % 2
            num, ind = pattern[pal][-1]
            if prev_num < num:
                break
            prev_num = num
            del(pattern[pal][-1])
            bit.add(ind, 1)
            ans_tmp += bit.get_sum(0, ind)
        else:
            ans = min(ans, ans_tmp)

if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush
import time
import copy
start = time.time()
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
X = []
for i in range(N):
    X.append((A[i],B[i]))
ans = -1
Q = [(0,X)]
while Q:
    if time.time()-start>1.7:break
    q = heappop(Q)
    A = [e[0] for e in q[1]]
    if A==sorted(A):
        ans=max(q[0],ans)
        break
    for i in range(N-1):
        Y = q[1][:]
        Y[i] = (q[1][i+1][1],q[1][i+1][0])
        Y[i+1] = (q[1][i][1],q[1][i][0])
        heappush(Q,(q[0]+1,Y))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))

    dg = 10**10

    dp = [[10**5]*n for i in range(2**n)]

    new = set([])
    for i in range(n):
        s = (1<<i)
        dp[s][i] = i
        new.add(s*dg+i)
    

    for k in range(n-1):
        tank = set([])
        if len(new) == 0:
            break
        for popelt in new:
            s,idx = popelt//dg,popelt%dg
            if (k-idx)%2 == 0:
                fr = a[idx]
            else:
                fr = b[idx]
            cnt = 0
            for j in range(n):
                if (s>>j)&1 == 0:
                    if (j-k)%2 == 1:
                        val = a[j]
                    else:
                        val = b[j]
                    if val >= fr:
                        dp[s+(1<<j)][j] = min(dp[s+(1<<j)][j],dp[s][idx]+j-cnt)
                        tank.add((s+(1<<j))*dg + j)
                else:
                    cnt += 1
            
        new = tank
    
    res = min(dp[2**n-1])

    if res == 10**5:
        print(-1)
    else:
        print(res)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))

    dg = 10**10

    dp = [[10**5]*n for i in range(2**n)]

    new = set([])
    for i in range(n):
        s = (1<<i)
        dp[s][i] = i
        new.add(s*dg+i)
    

    for k in range(n-1):
        tank = set([])
        for popelt in new:


            s,idx = popelt//dg,popelt%dg
            if (k-idx)%2 == 0:
                fr = a[idx]
            else:
                fr = b[idx]
            cnt = 0
            for j in range(n):
                if (s>>j)&1 == 0:
                    if (j-k)%2 == 1:
                        val = a[j]
                    else:
                        val = b[j]
                    if val >= fr:
                        dp[s+(1<<j)][j] = min(dp[s+(1<<j)][j],dp[s][idx]+j-cnt)
                        tank.add((s+(1<<j))*dg + j)
                else:
                    cnt += 1
            
        new = tank
    
    res = min(dp[2**n-1])

    if res == 10**5:
        print(-1)
    else:
        print(res)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

import itertools
n = inn()
a = inl()
b = inl()
cms = itertools.combinations(list(range(n)),n//2)
mn = BIG
for cm in cms:
    ev = []
    od = []
    for i in range(n):
        if i not in cm:
            ev.append((a[i] if i%2==0 else b[i], i))
        else:
            od.append((a[i] if i%2==1 else b[i], i))
    ev.sort()
    od.sort()
    #ddprint(f"{ev=}")
    #ddprint(f"{od=}")
    p = []
    q = []
    for i in range(n):
        if i%2==0:
            p.append(ev[i//2][1])
            q.append(ev[i//2][0])
        else:
            p.append(od[i//2][1])
            q.append(od[i//2][0])
    #ddprint(f"{cm=}")
    #ddprint(f"{p=}")
    #ddprint(f"{q=}")
    ok = True
    for i in range(n-1):
        if q[i]>q[i+1]:
            ok = False
            break
    if not ok:
        continue
    x = 0
    for i in range(n//2):
        #ddprint(f"{i=}")
        m = p.index(i)
        tmp = p[m]
        for j in range(m,i,-1):
            p[j] = p[j-1]
        p[i] = tmp
        x += m-i
        #ddprint(f"{m=} {p=}")
        m = p.index(n-1-i)
        tmp = p[m]
        for j in range(m,n-1-i):
            p[j] = p[j+1]
        p[n-1-i] = tmp
        x += n-1-i-m
        #ddprint(f"{m=} {p=}")
    #ddprint(f"{x=}")
    mn = min(mn,x)
print(mn if mn<BIG else -1)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
allpat=[]
todo=[[]]
while todo:
  pat=todo.pop()
  if len(pat)==n//2:
    allpat.append(pat)
    continue
  s=0
  if pat:s=max(pat)+1
  for i in range(s,n):
    todo.append(pat+[i])

def func(pat):
  # カードを最終的に偶奇どちらのidxになるかで分類
  # pat内のidxが最後に奇数のidxになるとする
  ablev=[]
  ablod=[]
  for i in range(n):
    if i in pat:
      if i%2==0:
        ablod.append([i,b[i]])
      else:
        ablod.append([i,a[i]])
    else:
      if i%2==0:
        ablev.append([i,a[i]])
      else:
        ablev.append([i,b[i]])
  ablev.sort(key=lambda x:x[1]*20+x[0])
  ablod.sort(key=lambda x:x[1]*20+x[0])
  now=0
  ary=[]
  for i in range(n//2):
    if ablev[i][1]>=now:
      now=ablev[i][1]
      ary.append(ablev[i][0])
    else:
      return -1
    if ablod[i][1]>=now:
      now=ablod[i][1]
      ary.append(ablod[i][0])
    else:
      return -1
  if n%2==1:
    if ablev[n//2][1]>=now:
      now=ablev[i][1]
      ary.append(ablev[n//2][0])
    else:
      return -1
  ret=0
  for i in range(n-1):
    for j in range(i+1,n):
      if ary[i]>ary[j]:ret+=1
  return ret

ans=float('inf')
for pat in allpat:
  t=func(pat)
  if t>=0:
    ans=min(ans,t)
print(ans if ans!=float('inf') else -1)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
allpat=[]
todo=[[]]
while todo:
  pat=todo.pop()
  if len(pat)==n//2:
    allpat.append(pat)
    continue
  s=0
  if pat:s=max(pat)+1
  for i in range(s,n):
    todo.append(pat+[i])

def func(pat):
  # カードを最終的に偶奇どちらのidxになるかで分類
  # pat内のidxが最後に奇数のidxになるとする
  ablev=[]
  ablod=[]
  for i in range(n):
    if i in pat:
      if i%2==0:
        ablod.append([i,b[i]])
      else:
        ablod.append([i,a[i]])
    else:
      if i%2==0:
        ablev.append([i,a[i]])
      else:
        ablev.append([i,b[i]])
  ablev.sort(key=lambda x:x[1]*20+x[0])
  ablod.sort(key=lambda x:x[1]*20+x[0])
  now=0
  ary=[]
  for i in range(n//2):
    if ablev[i][1]>=now:
      now=ablev[i][1]
      ary.append(ablev[i][0])
    else:
      return -1
    if ablod[i][1]>=now:
      now=ablod[i][1]
      ary.append(ablod[i][0])
    else:
      return -1
  if n%2==1:
    if ablev[n//2][1]>=now:
      now=ablev[i][1]
      ary.append(ablev[n//2][0])
    else:
      return -1
  ret=0
  for i in range(n):
    for j in range(n-1,i,-1):
      if ary[j-1]>ary[j]:
        ary[j],ary[j-1]=ary[j-1],ary[j]
        ret+=1
  return ret

ans=float('inf')
for pat in allpat:
  t=func(pat)
  if t>=0:
    ans=min(ans,t)
print(ans if ans!=float('inf') else -1)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def popcnt(n):
    return bin(n).count("1")

def main():
    n = int(ipt())
    card = [[int(i) for i in ipt().split()] for _ in range(2)]
#    n = 18
#    card = [[j*500-i*3+400 for j in range(18)] for i in range(2)]
    dp = [[10**18]*n for i in range(2**n)]

    for i in range(1,2**n):
        pi = popcnt(i)
        if pi == 1:
            for j in range(n):
                if (i>>j)&1:
                    dp[i][j] = 0
        else:
            pp = 0
            for j in range(n-1,-1,-1):
                if (i>>j)&1:
                    nn = card[(pi-j+1)%2][j]
                    pn = i-2**j
                    dpn = dp[pn]
                    for k in range(n):
                        if dp[i][j] > dpn[k]+pp:
                            if card[(pi-k)%2][k] <= nn:
                                dp[i][j] = dpn[k]+pp
                    pp += 1
    ans = min(dp[2**n-1])
    if ans == 10**18:
        ans = -1
    print(ans)
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import chain
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

def count_bit(x):
    res = 0
    while x:
        res += x % 2
        x >>= 1
    return res

def int2bin(x,N): 
    res = [0]*N
    for i in range(N):
        res[N-1-i] = x % 2
        x >>= 1
    return res

inf = 10**10
M = N//2 # the n of odd index
ans = inf
for b in range(2**N):
    valid = True 
    if count_bit(b) == M:
        odd_index = int2bin(b,N) # 1 : odd
        evens = []
        odds = []
        for i in range(N):
            if odd_index[i]:
                if i % 2:
                    odds.append((A[i],i))
                else:
                    odds.append((B[i],i))
            else:
                if i % 2:
                    evens.append((B[i],i))
                else:
                    evens.append((A[i],i))
        SE = sorted(evens)
        SO = sorted(odds)
        L = [None]*N
        L[::2] = SE
        L[1::2] = SO
        for (a,_),(b,_) in zip(L,L[1:]):
            if a > b:
                valid = False
                break
        if valid:
            L = list(zip(L,range(N)))
            L = sorted(L,key=lambda x : x[0][1])
            L = [(a,c) for (a,b),c in L]
            temp = 0
            for i in range(N):
                for j in range(i):
                    if L[j] > L[i]:
                        temp += 1
            ans = min(temp,ans)

if ans == inf:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations, combinations, chain
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

def dpinit(ps, val=0):
    import copy
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [copy.deepcopy(res) for k in [0]*i]
    return res

inf = 10**10
dp = [defaultdict(lambda : inf) for i in range(2**N+1)]
dp[0][0] = 0

for b in range(2**N):
    c = bin(b).count('1')
    for i in range(1,N+1):
        p = N-i
        f = 1<<p
        if b & f:
            continue
        nb = b | f
        k = bin(b % f).count('1')
        v = A[i-1] if (i-c) % 2 == 1 else B[i-1]
        for val, inv in dp[b].items():
            if val <= v:
                dp[nb][v] = min(dp[nb][v], inv+abs(c+1-(i+k)))

if not dp[2**N-1]:
    print(-1)
    exit()
ans = min(dp[2**N-1].values())
print(ans if ans != inf else -1)

Submission status: Accepted

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

dp = [[100100] * (1 << N) for _ in range(N)]
for i in range(N):
    dp[i][1 << i] = 0
for mask in range(1, 1 << N):
    mask_pop = format(mask, 'b').count('1')
    for j in range(N):
        if (1 << j) & mask:
            if (j - mask_pop) % 2 == 1:
                cur_elem = A[j]
            else: 
                cur_elem = B[j]
            prev_mask = mask & ~(1 << j)
            cost_delta = format(prev_mask & (-1 << j), 'b').count('1')
            for t in range(N):
                if (1 << t) & prev_mask:
                    prev_elem = A[t] if (t - mask_pop - 1) % 2 == 1 else B[t]
                    if prev_elem <= cur_elem:
                        if dp[j][mask] > dp[t][prev_mask] + cost_delta:
                            dp[j][mask] = dp[t][prev_mask] + cost_delta
            
# print(*dp, sep = '\n')

ans = min((dp[i][-1] for i in range(N)))
if ans == 100100:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

even = [a[i] if i % 2 == 0 else b[i] for i in range(n)]
odd = [a[i] if i % 2 == 1 else b[i] for i in range(n)]
ans = 1001001001
for s in combinations(range(n), n // 2):
    # s ... dest index is odd
    s = set(s)
    t = set(range(n)) - s
    sdest = [(odd[i], i) for i in s]
    tdest = [(even[i], i) for i in t]
    sdest.sort()
    tdest.sort()
    origs = []
    z = []
    for i in range(n):
        if i & 1 == 0:
            origs.append(tdest[i//2][1])
            z.append(tdest[i//2][0])
        else:
            origs.append(sdest[(i-1)//2][1])
            z.append(sdest[(i-1)//2][0])
    if not all(x <= y for x, y in zip(z, z[1:])):
        continue
    dests = [0] * n
    for dest, orig in enumerate(origs):
        dests[orig] = dest
    cnt = 0
    for i in range(n):
        for j in range(i):
            cnt += dests[j] > dests[i]
    ans = min(cnt, ans)

if ans == 1001001001:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
dp=[[10**9 for _ in range(51)] for _ in range(1<<N)]
dp[0][0]=0
for S in range(1<<N):
 j=bin(S).count("1")
 c=0
 for i in range(N):
  if not (S&1<<i):
   k = A[i] if (i-j)%2==0 else B[i]
   for l in range(k+1):
    dp[S|1<<i][k] = min(dp[S|1<<i][k],dp[S][l]+c)
   c += 1
ans = min(dp[-1])
print(-1 if ans == 10**9 else ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    
    n = ii()
    A, B = lmi(), lmi()
    L = [A, B]
    M = max(max(A), max(B))

    dp = [[inf] * (M+1) for _ in range(2 ** n)]
    dp[0][0] = 0

    for S in range(2 ** n):
        for k in range(M + 1):
            if dp[S][k] != inf:
                cnt = 0    # 何枚のカードがすでにあるか
                for i in range(n):
                    if S & (1 << i):
                        cnt += 1
                for i in range(n):
                    if not (S & (1 << i)):
                        card_front = L[(i - cnt) % 2][i]
                        if card_front < k:
                            continue
                        inv = 0
                        for j in range(i + 1, n):
                            if S & (1 << j):
                                inv += 1
                        dp[S | (1 << i)][card_front] = min(dp[S + (1 << i)][card_front], dp[S][k] + inv)

    # for line in dp:
    #     print(*line)

    ans = min(dp[S])
    if ans == inf:
        print(-1)
    else:
        print(ans)




if __name__ == "__main__":
    main()



"""
想定解は bit DP.

勉強のため解説のような bit DP で実装.
以下方針

- 並べ方を決めれば操作によらずどの数字が表に並ぶか決定可能
- 並べ方を全探索してそれぞれ昇順判定、転倒数計算をすると O(N! * N * NlgN)
- dp[S][k] = (すでに並べた集合 S, 最後のカードインデックス k のときのここまでの転倒数) とする
    - dp[0][0] = 0
    - それ以外 inf
    - 配る DP. dp[S][k] (k in S) から配布する. S に含まれぬカードインデックスについてそれを末尾に並べられるか判定
      並べられる場合、そのカードの転倒数を計算。dp[S+i][i] をもとの値との最小値で更新
    - 基本ループは 2^N, N の二重ループ。遷移のところでさらに O(N) の走査が入る。トータルで O(2^N * N^2)
"""

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def check_increasing(L):
        for i in range(1, n):
            if L[i][0] < L[i-1][0]:
                return False
        return True


    def modified_merge(left, right):
        '''
        ソート済み配列 left, right を受け取り、 O(n) で全体のソート済み配列を生成する
        マージの過程で転倒数をメモして返す

        >>> modified_merge([1, 5, 7], [2, 3, 3])
        (6, [1, 2, 3, 3, 5, 7])

        Args:
            left (list)
            right (list)
        Returns:
            inv (int)
            sorted_list (list)
        '''
        sorted_list = []
        i, j, inv = 0, 0, 0
        buf_1 = left[:] + [float('inf')]
        buf_2 = right[:] + [float('inf')]
        for _ in range(len(left) + len(right)):
            if buf_1[i] < buf_2[j]:
                sorted_list.append(buf_1[i])
                i += 1
                inv += j
            else:
                sorted_list.append(buf_2[j])
                j += 1
        return inv, sorted_list


    def modified_merge_sort(L, i, j):
        '''
        [i, j), つまりL[i:j] を O(nlgn) で非破壊的かつ安定にマージソートする
        マージソートの過程で転倒数をメモして返す
        
        >>> modified_merge_sort([3, 5, 2, 1, 0], 0, 5)
        (9, [0, 1, 2, 3, 5])

        Args:
            L (list)
            i (int)
            j (int)
        Returns:
            inv (int)
            sorted_list (list)
        '''
        if i + 1 == j:
            # L[i:j+1] = [L[i]]
            return 0, [L[i]]
        mid = (i + j) // 2
        left_inv_cnt, left = modified_merge_sort(L, i, mid)
        right_inv_cnt, right = modified_merge_sort(L, mid, j)
        merge_inv_cnt, sorted_list = modified_merge(left, right)
        return left_inv_cnt + right_inv_cnt + merge_inv_cnt, sorted_list


    def count_inversion(L):
        '''
        O(nlgn) で L の要素の転倒数を求める

        >>> count_inversion([1, 9, 2, 7, 5, 6, 4, 8, 3, 0])
        26
        '''
        cnt, _ = modified_merge_sort(L, 0, len(L))
        return cnt


    def calc_swapflip(L):
        return count_inversion(list(map(lambda x: x[1], L)))

    
    n = ii()
    A = lmi()
    B = lmi()

    ans = inf

    w = [(A[i], i, B[i]) if i % 2 == 0 else (B[i], i, A[i]) for i in range(n)]
    # w.sort(key=itemgetter(0))
    w.sort()

    for pattern in combinations(w, r=(n+1)//2):
        # print(pattern)
        left = [(elm[2], elm[1], elm[0]) for elm in w if elm not in pattern]
        # left.sort(key=itemgetter(0))
        left.sort()
        concat = []
        for i in range(n//2):
            concat.append(pattern[i])
            concat.append(left[i])
        if n % 2 == 1:
            concat.append(pattern[-1])

        if check_increasing(concat):
            op = calc_swapflip(concat)
            # print(concat)            
            # print(op)
            ans = min(ans, op)

    print(ans) if ans != inf else print(-1)
        




if __name__ == "__main__":
    main()