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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
AB = (A, B)
INF = 10**18

ans = INF
for state in range(1 << N):
    even = []
    odd = []

    for i in range(N):
        isReverse = (state & (1 << i)) >> i
        val = AB[isReverse][i]

        if i % 2 == 0:
            (even, odd)[isReverse].append((val, i))
        else:
            (odd, even)[isReverse].append((val, i))

    if len(even) != -(-N // 2) or len(odd) != N // 2:
        continue

    even.sort()
    odd.sort()
    odd.append((-1, -1))
    V = []
    P = []
    for (l, i), (r, j) in zip(even, odd):
        V.append(l)
        P.append(i)
        if r >= 0:
            V.append(r)
            P.append(j)

    if not all(l <= r for l, r in zip(V, V[1:])):
        continue

    cnt = 0
    for i, p in enumerate(P):
        for q in P[:i]:
            if p < q:
                cnt += 1
    ans = min(ans, cnt)

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

Solution (Python):

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


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()
    
    
    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])
    
    
    
    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):
        
        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
        
        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
        
    
    mn = min(mn,x)
print(mn if mn<BIG else -1)

Solution (Python):
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):
  
  
  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)

Solution (Python):
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):
  
  
  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)

Solution (Python):
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):
  
  
  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)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 
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)]


    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()

Solution (Python):
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 
ans = inf
for b in range(2**N):
    valid = True 
    if count_bit(b) == M:
        odd_index = int2bin(b,N) 
        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)

Solution (Python):
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)

Solution (Python):
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
            


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

Solution (Python):
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 = 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)

Solution (Python):
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)

Solution (Python):
INF = 10**9
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
dp = [[INF 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):
      if (i - j) % 2 == 0:
        k = A[i]
      else:
        k = 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 == INF else ans)

Solution (Python):
INF = 10000
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

dp = [[INF for i in range(N)] for j in range(1 << N)]

for i in range(N):
    dp[1 << i][i] = i

for i in range(1 << N):
    for j in range(N):
        if i >> j & 1:
            if (popcount(i) - j) % 2 != 0:
                num = A[j]
            else:
                num = B[j]
            cnt = 0
            for k in range(N):
                if not (i >> k & 1):
                    if (popcount(i) - k) % 2 == 0:
                        num2 = A[k]
                    else:
                        num2 = B[k]
                    if num <= num2:
                        dp[i | 1 << k][k] = min(dp[i | 1 << k][k], dp[i][j] + cnt)
                    cnt += 1

ans = INF
for i in range(N):
    ans = min(ans, dp[(1 << N) - 1][i])

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

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union






























def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    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)

    
    

    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)
"""

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union























from itertools import combinations, combinations_with_replacement

from operator import itemgetter              




def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    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:
            
            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()

    for pattern in combinations(w, r=(n+1)//2):
        
        left = [(elm[2], elm[1], elm[0]) for elm in w if elm not in pattern]
        
        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)
            
            
            ans = min(ans, op)

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




if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
nums = [None]*n


def init(bit, values):
    for i,v in enumerate(values):
        update(bit,i,v)

def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res


def update(bit,i,x):
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return



def tento(l):
    n = len(l)
    
    bit = [0] * (n+1)
    ans = 0
    for i,ind in enumerate(l):
        ans += (i - query(bit, ind+1))
        update(bit, ind+1, 1)
    return ans


def pp(func):
    def wrapped(*args, **keys):
        print(args, keys)
        val = func(*args, **keys)
        print(val)
        return val
    return wrapped


def sub(fr, to, bb):
    
    elist = []
    olist = []
    for ff,bbb in zip(fr, bb):
        if (ff+bbb)%2:
            olist.append(ff)
        else:
            elist.append(ff)

    elist2 = []
    olist2 = []
    for item in to:
        if item%2:
            olist2.append(item)
        else:
            elist2.append(item)
    if len(olist2)==len(olist) and len(elist2)==len(elist):
        olist.sort()
        elist.sort()
        if to[0]%2==0:
            res = [(elist if i%2==0 else olist)[i//2] for i in range(len(to))]
            return res
        else:
            res = [(olist if i%2==0 else elist)[i//2] for i in range(len(to))]
            return res
    else:
        return None
    
    
best = 10**9
for bit in range(1<<n):
    for i in range(n):
        val = b[i] if bit>>i&1 else a[i]
        nums[i] = (val, i, bit>>i&1)
    nums.sort()
    prev, fr, bb = nums[0]
    to = [0]
    fr = [fr]
    bb = [bb]
    valid = True
    array = []
    for i in range(1,n):
        cv, cfr, cbb = nums[i]
        if prev!=cv:
            res = sub(fr, to, bb)
            if res is None:
                valid = False
                break
            array.extend(res)
            prev, fr, bb = cv, [cfr], [cbb]
            to = [i]
        else:
            fr.append(cfr)
            to.append(i)
            bb.append(cbb)
    else:
        res = sub(fr, to, bb)
        if res is None:
            valid = False
        else:
            array.extend(res)
    if valid:
        ans = tento(array)

        best = min(best, ans)

if best==10**9:
    print(-1)
else:
    print(best)

Solution (Python):

import sys
from itertools import permutations,combinations
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


INF = 10 ** 5
answer = INF
N = ir()
if N == 1:
    print(0); exit()
A = lr()
B = lr()
for pattern in combinations(range(N), (N+1)//2):
    pattern = set(pattern)
    red = []
    blue = []
    for i in range(N):
        if i in pattern:
            red.append((B[i], i) if i&1 else (A[i], i))
        else:
            blue.append((A[i], i) if i&1 else (B[i], i))
    red.sort()
    blue.sort()
    result = []
    
    for i in range(N//2):
        if red[i][0] > blue[i][0]:
            break
        if i + 1 < len(red) and red[i+1][0] < blue[i][0]:
            break
        result.append(red[i][1])
        result.append(blue[i][1])
    else:
        if N&1 and blue[-1][0] > red[-1][0]:
            continue
        if N&1:
            result.append(red[-1][1])
        temp = 0
        used = set()
        for i in range(N):
            for x in used:
                if result[i] < x:
                    temp += 1
            used.add(result[i])            
        if temp < answer:
            answer = temp

print(answer if answer != INF else -1)