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 = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AB = sorted(list(set(A + B)))
D = {ab: i+1 for i, ab in enumerate(AB)}
A = [D[a] for a in A]
B = [D[a] for a in B]
def chk(L):
    NN = 5
    BIT=[0] * (2**NN+1)
    def addbit(i):
        while i <= 2**NN:
            BIT[i] += 1
            i += i & (-i)
 
    def getsum(i):
        ret = 0
        while i != 0:
            ret += BIT[i]
            i -= i&(-i)
        return ret
    s = 0
    for l in L[::-1]:
        s += getsum(l+1)
        addbit(l+1)
    return s
ans = 1 << 100
for m in range(1<<N):
    if bin(m).count("1") & 1: continue
    C = [[], []]
    for i in range(N):
        p = m >> i & 1
        q = p + i & 1
        C[q].append(((A[i] if p == 0 else B[i]) << 5) + i)
    if len(C[1]) != N // 2: continue
    C[0].sort()
    C[1].sort()
    CC = [C[i&1][i//2] for i in range(N)]
    for i in range(1, N):
        if CC[i-1] >> 5 > CC[i] >> 5: break
    else:
        CCC = [c % 32 for c in CC]
        ans = min(ans, chk(CCC))
print(ans if ans < 1 << 100 else -1)

Solution (Python):
import itertools
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 invnum(n,a):
    bit=Bit(n)
    res=0
    for j in range(n):
        res+=j-bit.sum(a[j])
        bit.add(a[j],1)
    return res
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
flag=0
M=-1
if N%2==0:
    M=N//2
else:
    M=N//2+1
ans=(N*(N-1))//2
for seq in itertools.combinations(range(N),M):
    X=[]
    Y=[]
    era=[0 for i in range(N)]
    for i in seq:
        if i%2==0:
            X.append((A[i],i))
        else:
            X.append((B[i],i))
        era[i]=1
    for i in range(N):
        if era[i]==0:
            if i%2==0:
                Y.append((B[i],i))
            else:
                Y.append((A[i],i))
    X.sort()
    Y.sort()
    L=[]
    if N%2==1:
        for i in range(M-1):
            L.append(X[i])
            L.append(Y[i])
        L.append(X[-1])
    else:
        for i in range(M):
            L.append(X[i])
            L.append(Y[i])
    
    flag2=1
    for i in range(N-1):
        if L[i][0]>L[i+1][0]:
            flag2=0
            break
    if flag2==1:
        flag=1
        S=[L[i][1]+1 for i in range(N)]
        tmp=invnum(N,S)
        ans=min(tmp,ans)
if flag==1:
    print(ans)
else:
    print(-1)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def swap(l):
    cnt = 0
    now = list(range(n))
    for i in range(n):
        c = l[n-i-1]
        n_ind = now.index(c)
        
        cnt += abs((n-i-1)-n_ind)
        if (n-i-1)-n_ind == 0:
            continue
        now.remove(c)
        
        now.insert(n-i-1,c)
        
    return cnt

n = inp()
a = inpl()
b = inpl()
card = []
res = INF
for i in range(n):
    card.append([a[i],b[i],i])
for flag in itertools.combinations(range(n),(n+1)//2):
    
    f = True
    odd_li = []
    odd_ind = [False] * n
    for i,bit in enumerate(flag):
        c = 1 if bit%2 else 0
        odd_li.append([card[bit][c],bit])
        odd_ind[bit] = True
    if not f:
        continue
    odd_li.sort()
    even_li = []
    for i in range(n):
        c = 0 if i%2 else 1
        if not odd_ind[i]:
            even_li.append([card[i][c],i])
    even_li.sort()
    

    if n%2:
        for i in range(n//2):
            if odd_li[i][0] <= even_li[i][0] <= odd_li[i+1][0]:
                continue
            else:
                f = False; break
    else:
        for i in range(n//2):
            if i != n//2-1:
                if odd_li[i][0] <= even_li[i][0] <= odd_li[i+1][0]:
                    continue
                else:
                    f = False; break
            else:
                if odd_li[-1][0] <= even_li[-1][0]:
                    continue
                else:
                    f = False; break

    if f:
        after_ind = []
        for i in range(n//2):
            after_ind.append(odd_li[i][1])
            after_ind.append(even_li[i][1])
        if n%2:
            after_ind.append(odd_li[-1][1])
        
        
        res = min(res,swap(after_ind))
print(-1 if res == INF else res)

Solution (Python):

N = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = float("inf")

for ii in range(2 ** N):

    s = format(ii,'b').zfill(N)
    on = 0
    
    for j in s:
        if j == "1":
            on += 1

    if on != (N+1)//2:
        continue

    q = []
    q2 = []

    for i in range(N):
        if s[i] == "1":
            if i % 2 == 0:
                q.append([A[i],i])
            else:
                q.append([B[i],i])
        else:
            if i % 2 != 0:
                q2.append([A[i],i])
            else:
                q2.append([B[i],i])           

    q.sort()
    q2.sort()
    q2.append([float("inf"),0])
    

    flag = True
    nmax = 0

    for i in range((N+1)//2):


        if nmax > q[i][0]:
            flag = False
        nmax = q[i][0]

        if nmax > q2[i][0]:
            flag = False
        nmax = q2[i][0]

    if flag:
        r = []
        for i in range((N+1)//2):
            r.append(q[i][1])
            r.append(q2[i][1])

        

        now = 0
        z = [i for i in range(N)]
        for i in range(N):
            for j in range(len(z)):
                if z[j] == r[i]:
                    now += j
                    del z[j]
                    break
            
        ans = min(now,ans)

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

N = int(readline())
A = list(map(int,readline().split()))
B = list(map(int,readline().split()))

class BinaryIndexedTree():
    def __init__(self, seq):
        self.size = len(seq)
        self.depth = self.size.bit_length()
        self.build(seq)
        
    def build(self,seq):
        data = seq
        size = self.size
        for i,x in enumerate(data):
            j = i+(i&(-i))
            if j < size:
                data[j] += data[i]
        self.data = data
        
    def __repr__(self):
        return self.data.__repr__()
        
    def get_sum(self,i):
        data = self.data
        s = 0
        while i:
            s += data[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        data = self.data
        size = self.size
        while i < size:
            data[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        data = self.data; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + data[y]
            if sy < k:
                x,sx = y,sy
        return x + 1

def Inversion(seq):
    
    N = len(seq)
    bit = BinaryIndexedTree([0] * (N+1))
    inv = N*(N-1)//2
    for x in seq:
        inv -= bit.get_sum(x)
        bit.add(x,1)
    return inv

INF = 10 ** 9
answer = INF
for I in itertools.combinations(range(N),(N+1)//2):
    J = [j for j in range(N) if j not in I]
    ODD = [(B[i] if i&1 else A[i],i) for i in I]
    EV = [(A[i] if i&1 else B[i],i) for i in J]
    ODD.sort()
    EV.sort()
    ind = [0] * N
    seq = [0] * N
    for i in range(0,N,2):
        seq[i], ind[i] = ODD[i//2]
    for i in range(1,N,2):
        seq[i], ind[i] = EV[i//2]
    if not all(x<= y for x,y in zip(seq,seq[1:])):
        continue
    ind = [x+1 for x in ind]
    n = Inversion(ind)
    if answer > n:
        answer = n

if answer == INF:
    answer = -1
print(answer)

Solution (Python):
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]))
        
        
        if ng():continue
        kk=[]
        for [_,_,i0],[_,_,i1] in zip(xx0,xx1):
            kk+=[i0,i1]
        if n%2:kk+=[xx0[-1][2]]
        
        ans=change(ans)
        
    if ans==1000:print(-1)
    else:print(ans)

main()

Solution (Python):
def main():
    import sys
    from itertools import combinations
    from operator import itemgetter
    input = sys.stdin.readline

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

    even = []
    odd = []
    for i in range(N):
        if i%2:
            odd.append(A[i])
            even.append(B[i])
        else:
            even.append(A[i])
            odd.append(B[i])

    L = list(range(N))
    ans = 10**9
    for v in combinations(L, N//2):
        ok = 1
        tmp = []
        tmp_odd = []
        tmp_even = []
        for i in range(N):
            if i in v:
                tmp.append(odd[i] * 100)
                tmp_odd.append((odd[i], i))
            else:
                tmp.append(even[i] * 100)
                tmp_even.append((even[i], i))

        tmp_odd.sort(key=itemgetter(0))
        tmp_even.sort(key=itemgetter(0))

        tmp_check = []
        p = [0] * N
        for i in range(N):
            if i%2:
                tmp_check.append(tmp_odd[i//2][0])
                p[tmp_odd[i//2][1]] = i
            else:
                tmp_check.append(tmp_even[i // 2][0])
                p[tmp_even[i // 2][1]] = i
        for i in range(N-1):
            if tmp_check[i] > tmp_check[i+1]:
                ok = 0
                
                break
        if not ok:
            continue

        for i in range(N):
            tmp[i] += p[i]

        ans_new = 0
        for i in range(N):
            for j in range(i+1, N):
                if tmp[i] > tmp[j]:
                    ans_new += 1
        
        ans = min(ans, ans_new)

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


if __name__ == '__main__':
    main()

Solution (Python):
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]))
        
        
        if ng():continue
        kk=[]
        for [_,_,i0],[_,_,i1] in zip(xx0,xx1):
            kk+=[i0,i1]
        if n%2:kk+=[xx0[-1][2]]
        
        ans=change(ans)
        
    if ans==1000:print(-1)
    else:print(ans)

main()

Solution (Python):

import sys
input = sys.stdin.readline

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

odd_bit = 0b0101010101010101010101
eve_bit = 0b1010101010101010101010
full_bit = 2**n - 1

odd_num = (n + 1) // 2
ans = 10**9 

for i in range(2**n):
    invi = full_bit ^ i
    odd = bin(i & odd_bit).count("1") + bin(invi & eve_bit).count("1")
    if odd != odd_num:
        continue
    odd_card = []
    eve_card = []
    for j in range(n):
        if i & 1 << j:
            if j % 2 == 0:
                odd_card.append((a[j], j))
            else:
                eve_card.append((a[j], j))
        else:
            if j % 2 == 0:
                eve_card.append((b[j], j))
            else:
                odd_card.append((b[j], j))
    odd_card.sort()
    eve_card.sort()
    odd_itr = 0
    eve_itr = 0
    curr = 0
    val = 0
    ok = True
    perm = []
    for i in range(n):
        if i % 2 == 0:
            num, index = odd_card[odd_itr]
            perm.append(index)
            odd_itr += 1
        else:
            num, index = eve_card[eve_itr]
            perm.append(index)
            eve_itr += 1
        if num < curr:
            ok = False
            break
        curr = num
    if ok:
        val = 0
        visited = [0] * n
        itr = 0
        for item in perm:
            visited[item] = 1
            val += itr - sum(visited[:item])
            itr += 1
        ans = min(ans, val)

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

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

odds = []
evens = []
for i in range(n):
    if i%2 == 0:
        odds.append([a[i],i])
        evens.append([b[i],i])
    else:
        odds.append([b[i],i])
        evens.append([a[i],i])

odds = sorted(odds)
evens = sorted(evens)



inds = [i for i in range(n)]

ans = 10000000000
exist = 0

half = (n-1)//2 + 1
for v in  itertools.combinations(inds,half):
    

    
    real_v = [odds[i][1] for i in v]
    
    real_nokori = []

    for i in range(n):
        if not (evens[i][1] in real_v):
            real_nokori.append(evens[i][1])
    
    nokori = []
    for i in range(n):
        if evens[i][1] in real_nokori:
            nokori.append(i)

    


    moge = 1
    if n%2 == 0:
        for i in range(half):
                if evens[nokori[i]][0] < odds[v[i]][0]:
                    moge = 0
    else:
        for i in range(n-half):
                if evens[nokori[i]][0] < odds[v[i]][0]:
                    moge = 0

    for i in range(half-1):
        if evens[nokori[i]][0] > odds[v[i+1]][0]:
            moge = 0

    if moge != 1:
        continue
    else:
        exist = 1

    tar = []
    for i in range(n):
        if i%2 == 0:
            tar.append(real_v[i//2])
        else:
            tar.append(real_nokori[(i-1)//2])
    dist = 0
    for i in range(n):
        for mo in range(i+1,n):
            if tar[mo] < tar[i]:
                dist += 1
    if dist < ans:
        ans = dist
if exist:
    print(ans)
else:
    print(-1)

Solution (Python):
N = int(input())
*A, = map(int,input().split())
*B, = map(int,input().split())

INF = N *100
ans = INF
for i in range(2**N):
    C = [((a,j,0) if (i>>j)&1 else (b,j,1)) for j,a,b in zip(range(N),A,B)]
    P = sum(p for c,j,p in C)
    if P%2: continue
    E = sum(p for c,j,p in C[::2])
    O = sum(p for c,j,p in C[1::2])
    if E!=O: continue
    C0 = []
    C1 = []
    for c,j,p in C:
        if (p+j)%2:
            C1.append((c,j,p))
        else:
            C0.append((c,j,p))
    C0.sort()
    C1.sort()
    D = []
    E = []
    for c0,c1 in zip(C0,C1):
        E.append(c0[0])
        E.append(c1[0])
        D.append(c0[1])
        D.append(c1[1])
    if N%2:
        D.append(C0[-1][1])
        E.append(C0[-1][0])
    contFlg = False
    for e,e2 in zip(E[:-1],E[1:]):
        if e>e2:
            contFlg = True
            break
    if contFlg: continue
    tmp = 0
    for i,d in enumerate(D):
        for j,d2 in enumerate(D[:i]):
            if d2 > d: tmp += 1
    ans = min(ans,tmp)
if ans == INF:
    ans = -1
print(ans)

Solution (Python):
from itertools import combinations
import sys
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a2=list()
b2=list()

if n==1:
    print(0)
    sys.exit()
    
for i in range(n):
    if i%2:
        b2.append(a[i])
        a2.append(b[i])
    else:
        a2.append(a[i])
        b2.append(b[i])

ans=10**9
for idx in combinations(range(0,n), (n+1)//2):
    a3=list()
    b3=list()
    flag=True
    for i in range(n):
        if i in idx:
            a3.append([a2[i], i])
        else:
            b3.append([b2[i], i])
    a3.sort(key=lambda x:x[0])
    b3.sort(key=lambda x:x[0])

    for i in range(len(b3)-1):
        if a3[i][0]>b3[i][0] or a3[i+1][0]<b3[i][0]:
            flag=False
    if len(a3)>len(b3):
        if a3[-1][0]<b3[-1][0] or a3[-2][0]>b3[-1][0]:
            flag=False
    elif a3[-1][0]>b3[-1][0]:
        flag=False

    if flag:
        ansidx = list()
        for i in range(len(b3)):
            ansidx.append(a3[i][1])
            ansidx.append(b3[i][1])
        if len(a3)>len(b3):
            ansidx.append(a3[-1][1])

        swap=0
        for i in range(n):
            for j in range(i,n):
                if ansidx[i]>ansidx[j]:
                    swap+=1
        ans= min(ans, swap)

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

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

o=N//2
e=N-o

import itertools
E=[]
O=[]
for i in range(N):
    if i%2==0:
        E.append(i)
    else:
        O.append(i)
ANS=10000

def mergecount(Z):
    cnt1 = 0
    z = len(Z)
    if z>1:
        A1 = Z[:z>>1]
        A2 = Z[z>>1:]
        cnt1 += mergecount(A1)
        cnt1 += mergecount(A2)
        i1=0
        i2=0
        for i in range(z):
            if i2 == len(A2):
                Z[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                Z[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                Z[i] = A1[i1]
                i1 += 1
            else:
                Z[i] = A2[i2]
                i2 += 1
                cnt1 += z//2 - i1
    return cnt1

for i in range(o+1):
    X=list(itertools.combinations(E,i))
    Y=list(itertools.combinations(O,i))
    for j in range(len(X)):
        for k in range(len(Y)):
            ev=[]
            od=[]
            for n in range(N):
                if n%2==0:
                    if n in X[j]:
                        od.append([B[n],n])
                    else:
                        ev.append([A[n],n])
                else:
                    if n in Y[k]:
                        ev.append([B[n],n])
                    else:
                        od.append([A[n],n])
            ev.sort()
            od.sort()
            
            Z=[]
            Num=0
            F=0
            for x in range(N):
                if x%2==0:
                    if Num>ev[x//2][0]:
                        F=1
                        break
                    else:
                        Num=ev[x//2][0]
                        Z.append(ev[x//2][1])
                else:
                    if Num>od[x//2][0]:
                        F=1
                        break
                    else:
                        Num=od[x//2][0]
                        Z.append(od[x//2][1])
            if F==0:
                
                tcnt=mergecount(Z)
            if F==0 and tcnt<ANS:
                ANS=tcnt
                
if ANS==10000:
    print(-1)
else:
    print(ANS)

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict
import itertools




class BIT:
	def __init__(self, N):
		self.size = N
		self.tree = [0] * (N + 1)

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

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


def getlist():
	return list(map(int, input().split()))


def main():
	
	N = int(input())
	A = getlist()
	B = getlist()
	omote = []
	ura = []
	for i in range(N):
		if i % 2 == 0:
			omote.append([A[i], i])
			ura.append([B[i], i])
		else:
			omote.append([B[i], i])
			ura.append([A[i], i])

	
	seq = [i for i in range(N)]
	alllist = list(itertools.combinations(seq, int((N + 1) // 2)))
	M = len(alllist)
	
	ans = float("inf")
	for i in range(M):
		lis = alllist[i]
		USE = [0] * N
		for j in lis:
			USE[j] = 1 
		X = []
		Y = []
		for j in range(N):
			if USE[j] == 1:
				X.append(omote[j])
			else:
				Y.append(ura[j])
		X = sorted(X)
		Y = sorted(Y)
		sequence = []
		for j in range(N):
			if j % 2 == 0:
				sequence.append(X[int(j // 2)])
			else:
				sequence.append(Y[int(j // 2)])
		
		judge = "Yes"
		for j in range(N - 1):
			if sequence[j][0] > sequence[j + 1][0]:
				judge = "No"
				break
		if judge == "Yes":
			bit = []
			for j in range(N):
				bit.append(sequence[j][1] + 1)
			
			val = 0
			calc = BIT(50)
			for j in range(N):
				calc.add(bit[j], 1)
				val += j + 1 - calc.sum(bit[j])
			
			ans = min(ans, val)

	if ans == float("inf"):
		print(-1)
	else:
		print(ans)














if __name__ == '__main__':
	main()

Solution (Python):
def iter_bit(k, LIMIT):
    v = (1 << k) - 1

    while v < LIMIT:
        yield v
        x = v & -v
        y = v + x
        v = (v & ~y) // x >> 1 | y


def solve(n, cards):
    dp = [{} for _ in range(1 << n)]
    dp[-1][0] = 0
    LIMIT = 1 << n

    for d in range(n):
        for state in iter_bit(n - d, LIMIT):
            scores = dp[state]
            k = state
            curr = 0
            while k:
                b = k & -k
                i = b.bit_length() - 1
                num = cards[i][(d - i) % 2]
                next_dp = dp[state ^ b]
                for left_num, score in scores.items():
                    if left_num > num:
                        continue
                    ns = score + curr
                    if num not in next_dp or next_dp[num] > ns:
                        next_dp[num] = ns
                k ^= b
                curr += 1

    if len(dp[0]) > 0:
        return min(dp[0].values())
    else:
        return -1


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))

Solution (Python):
from collections import defaultdict

def main():

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

    if all(a[0] == a[i] for i in range(n)):
        print(0)
        exit()

    pre = [1<<i for i in range(n)]
    bitcnt = [0]*(1<<n)
    bitcnt[1] = 1
    for i in range(1<<(n-1)):
        bitcnt[2*i] = bitcnt[i]
        bitcnt[2*i+1] = bitcnt[i]+1

    DP = [defaultdict(lambda : float("inf")) for i in range(n)]

    for i in range(n):
        DP[i][1<<i] = 0
    s = defaultdict(lambda : float("inf"))
    for i in range(n-1):
        nxt = [defaultdict(lambda : float("inf")) for i in range(n)]
        for j in range(n):
            last = a[j] if (i-j)%2 == 0 else b[j]
            for state, cost in DP[j].items():
                for to in range(n):
                    if state>>to&1:
                        continue
                    nlast = a[to] if (i+1-to)%2 == 0 else b[to]
                    if last > nlast:
                        continue
                    nstate = state|pre[to]
                    ncost = cost
                    ncost += bitcnt[state>>to]
                    if s[(nstate, nlast)] <= ncost:
                        continue
                    s[(nstate, nlast)] = ncost
                    if nxt[to][nstate] > ncost:
                        nxt[to][nstate] = ncost
        DP = nxt
    mask = (1<<n)-1
    ans = float("inf")
    for i in range(n):
        ans = min(ans, DP[i][mask])
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

res = []

for bit in range(2 ** n):
    if str(bin(bit)).count('1') % 2 == 1:
        continue

    odds = []
    evens = []
    for i in range(n):
        if (bit >> i) & 1:
            card = B[i]
            check = (i + 1) % 2

        else:
            card = A[i]
            check = i % 2

        if check == 1:
            odds.append([card, i+1])
        else:
            evens.append([card, i+1])

    if 0 <= len(evens) - len(odds) <= 1:
        odds.sort(reverse=True)
        evens.sort(reverse=True)
        now = 0
        pattern = []
        for _ in range(len(evens)):
            num1, idx1 = evens.pop()

            if now <= num1:
                now = num1
                pattern.append(idx1)
                if odds:
                    num2, idx2 = odds.pop()
                    if now <= num2:
                        now = num2
                        pattern.append(idx2)
                    else:
                        break

            else:
                break
        else:
            res.append(pattern)


if not res:
    print(-1)
    exit()

ans = []
for pattern in res:
    count = 0
    for i in range(n-1):
        num = pattern[i]
        check = pattern[i+1:]
        for t in check:
            if t < num:
                count += 1

    ans.append(count)

print(min(ans))

Solution (Python):


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

    dg = 20

    pp = 20

    dp = [10**5]*(10**7)

    new = set([])
    for i in range(n):
        s = (1<<i)
        dp[s*pp+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 and dp[(s+(1<<j))*pp+j] > dp[s*pp+idx]+j-cnt:
                        dp[(s+(1<<j))*pp+j] = dp[s*pp+idx]+j-cnt
                        tank.add((s+(1<<j))*dg + j)
                else:
                    cnt += 1
        new = tank
    
    res = 10**5
    s = (2**n-1)*pp
    for i in range(n):
        if res > dp[s+i]:
            res = dp[s+i]
    if res == 10**5:
        print(-1)
    else:
        print(res)


if __name__ == '__main__':
    main()