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


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def pop_count(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
cards = [[]] * 2
cards[0] = LIST()
cards[1] = LIST()


dp = list2d(1<<N, N, INF)
for i in range(N):
    
    dp[1<<i][i] = 0
for S in range(1, 1<<N):
    popcnt = pop_count(S)
    
    acc = [0] * N
    for i in range(N):
        if S & 1<<i:
            acc[i] = 1
    
    acc = list(accumulate(acc[::-1]))[::-1]
    for i in range(N):
        if dp[S][i] == INF or not S & 1<<i:
            continue
        
        cur = cards[(i%2)^(1-popcnt%2)][i]
        for j in range(N):
            if S & 1<<j:
                continue
            
            nxt = cards[(j%2)^(popcnt%2)][j]
            
            if cur <= nxt:
                
                dp[S|1<<j][j] = min(dp[S|1<<j][j], dp[S][i] + acc[j])
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):
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = N ** 2
for i in range(1 << N):
  L = [[] for _ in range(N)]
  T = [0] * N
  t = i
  for j in range(N):
    if t & 1:
      L[j] = [A[j], 1]
      T[j] = A[j]
    else:
      L[j] = [B[j], 0]
      T[j] = B[j]
    t >>= 1
  D = [0] * N
  T.sort()
  cnt = 0
  for j in range(N):
    c = 0
    for k in range(N):
      if D[k] == 0:
        if L[j][0] == T[k] and (j + 1 - L[j][1]) % 2 == k % 2:
          D[k] = 1
          cnt += j - c
          break
      else:
        c += 1
    else:
      break
  else:
    ans = min(ans, cnt)

if ans == N ** 2:
  print(-1)
else:
  print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def pop_count(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
cards = [[]] * 2
cards[0] = LIST()
cards[1] = LIST()

ans = INF
for S in range(1<<N):
    
    if pop_count(S) % 2 != 0:
        continue
    
    A1 = [[] for i in range(2)]
    for i in range(N):
        
        if S & 1<<i:
            A1[(i%2)^1].append((cards[1][i], i))
        
        else:
            A1[i%2].append((cards[0][i], i))
    
    if len(A1[0]) != ceil(N, 2) or len(A1[1]) != N // 2:
        continue
    
    A1[0].sort(reverse=1)
    A1[1].sort(reverse=1)
    cnt = 0
    A2 = [0] * N
    idxs = [0] * N
    for i in range(N):
        
        A2[i], idxs[i] = A1[i%2].pop()
    
    if A2 == sorted(A2):
        
        cnt = 0
        for i, idx1 in enumerate(idxs):
            for j, idx2 in enumerate(idxs[i+1:], i+1):
                if idx1 > idx2:
                    cnt += 1
        ans = min(ans, cnt)
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
INF = N**3
max_ab = max(max(A),max(B))+1
dp = [[INF] * max_ab for _ in range(2**N)]
dp[0][0]=0
for i in range(2**N):
  done = 0
  for j in range(N):
    if (i>>j)&1:
      done += 1
  
  for right_end in range(max_ab):
    if dp[i][right_end]==INF:
      continue
    for add_last in range(N):
      if (i>>add_last)&1:
        continue
      if abs(add_last-done)%2==0:
        add_last_surface = A[add_last]
      else:
        add_last_surface = B[add_last]
        
      if right_end>add_last_surface:
        continue
        
      num = 0
      for k in range(add_last):
        if (i>>k)&1==0:
          num+=1
          
      dp[i|1<<add_last][add_last_surface]=min(dp[i|1<<add_last][add_last_surface],
                                              dp[i][right_end]+num)
      
ans = min(dp[-1])
if ans==INF:
  print(-1)
else:
  print(ans)

Solution (Python):
def main():
  N = int(input())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  
  M = max(max(A),max(B))+1
  INF=float('inf')
  
  dp = [[INF for _ in range(M)] for _ in range(1<<N)]
  dp[0][0] = 0
  
  for i in range(1<<N):
    
    idx = 0
    for k in range(N):
      
      if (i>>k)&1 == 1:
        idx += 1
    for j in range(M):
      if dp[i][j] >= INF:
        continue
      for k in range(N):
        
        
        if (i>>k)&1:
          continue
        
        
        if abs(k-idx)%2 == 0:
          c = A[k]
        else:
          c = B[k]
  
        
        if j > c:
          continue
        
        
        
        t = 0
        for l in range(k):
          if (i>>l)&1 == 0:
            t += 1
        
        dp[i|(1<<k)][c] = min(dp[i|(1<<k)][c],dp[i][j]+t)
  
  ans = INF
  for i in range(M):
    ans = min(dp[(1<<N)-1][i],ans)
  print(ans if ans < INF else -1)

if __name__ == '__main__':
  main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ab=lambda i,j:a[i] if abs(i-j)%2==0 else b[i]
inf=10**9
dp=[n*[inf]for _ in range(1<<n)]
dp[0][0]=0
for i in range(n):dp[1<<i][i]=i
for bit in range(1,1<<n):
  m=[0]*n
  ii=0
  for i in range(n):
    if bit&1<<i:
      m[i]=ii
      ii+=1
  bit_count=ii
  for i in range(n):
    if bit&1<<i==0:
      m[i]=ii
      ii+=1
  for i in range(n):
    if bit&1<<i:continue
    ci=ab(i,bit_count)
    for j in range(n):
      if bit&1<<j==0:continue
      cj=ab(j,bit_count-1)
      if cj>ci:continue
      dp[bit|(1<<i)][i]=min(dp[bit|(1<<i)][i],dp[bit][j]+m[i]-bit_count)
ans=inf
for i in range(n):ans=min(ans,dp[-1][i])
if ans==inf:ans=-1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def count(P):
    res = 0
    
    BIT = [0]*(N+1)

    
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return


    Pi = [None]*N
    for i in range(N):
        Pi[P[i]] = i
    for i in range(N):
        p = Pi[i]
        res += i-BIT_query(p+1)
        BIT_update(p+1, 1)
    return res
 

N = int(input())
A = tuple(map(int,input().split()))
B = tuple(map(int,input().split()))
uhalf = -(-N//2)
dhalf = N - uhalf
inf = 10**9+7
ans = inf
for S in range(1<<N):
    card = [A[i] if S&(1<<i) else B[i] for i in range(N)]
    parity = [(1&(S>>i))^(i&1) for i in range(N)]
    even = [(card[i], i) for i in range(N) if parity[i]]
    odd = [(card[i], i) for i in range(N) if not parity[i]]
    if len(even) != uhalf or len(odd) != dhalf:
        continue
    even.sort()
    odd.sort()
    if any(e[0] > o[0] for e, o in zip(even, odd)) or any(e[0] < o[0] for e, o in zip(even[1:], odd)):
        continue
    perm = [even[i//2][1] if not i&1 else odd[i//2][1] for i in range(N)]
    ans = min(ans, count(perm))
print(ans if ans < inf else -1)

Solution (Python):
def main():
  N = int(input())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  
  M = max(max(A),max(B))+1
  
  INF = float('inf')
  
  dp = [[INF for _ in range(M)] for _ in range(1<<N)]
  dp[0][0] = 0
  
  for i in range(1<<N):
    
    idx = 0
    for k in range(N):
      if (i>>k)&1 == 1:
        idx += 1
    for j in range(M):
      if dp[i][j] >= INF:
        continue
      for k in range(N):
        
        
        if i&(1<<k) == 1:
          continue
        
        
        if abs(k-idx)%2 == 0:
          c = A[k]
        else:
          c = B[k]
  
        
        if j > c:
          continue
        
        
        
        t = 0
        for l in range(k):
          if (i>>l)&1 == 0:
            t += 1
        
        dp[i|(1<<k)][c] = min(dp[i|(1<<k)][c],dp[i][j]+t)
  
  
  ans = INF
  for i in range(M):
    ans = min(dp[(1<<N)-1][i],ans)
  print(ans if ans < INF else -1)

if __name__ == '__main__':
  main()

Solution (Python):

import sys
from collections import defaultdict
INF = float("inf")


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


def solve(N: int, A: "List[int]", B: "List[int]"):

    DP = [[INF]*51 for _ in range(1 << N)]
    DP[0][0] = 0

    for bit in range(1 << N):

        ketawa = bit_sum(bit)

        
        rest = []
        counter = ketawa
        for i in range(N):
            if bit & (1 << i):
                continue
            rest.append((i, counter))
            counter += 1

        
        for s in range(51):
            if DP[bit][s] == INF:
                continue
            for orig, curr in rest:
                
                
                if (orig-ketawa) % 2 == 0:
                    front = A[orig]
                else:
                    front = B[orig]
                
                if front >= s:
                    DP[bit | 1 << orig][front] = min(DP[bit | 1 << orig][front],
                                                     DP[bit][s]+abs(curr-ketawa))
    ans = min(DP[-1])
    if ans == INF:
        print(-1)
    else:
        print(ans)


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    B = [int(next(tokens)) for _ in range(N)]  
    solve(N, A, B)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
judge = False
ans = 10**9
for i in range(2**N):
  even = []
  odd = []
  x = 0
  tmp = True
  for j in range(N):
    if ((i>>j) & 1):
      if j%2==1:
        even.append([B[j],j])
      else:
        odd.append([B[j],j])
      
    else:
      if j%2==1:
        odd.append([A[j],j])
      else:
        even.append([A[j],j])
        
  if N%2==0:
    if len(even)!=len(odd):
      continue
      
  else:
    if (len(even)-1)!=len(odd):
      continue
      

  even = sorted(even,key = lambda x:x[0])
  odd = sorted(odd,key = lambda x:x[0])
  ind = [0]*N
  for k in range(N//2):
    o = odd[k]
    e = even[k]
    if o[0]<e[0]:
      tmp = False
      break
    
    if (k!=N//2-1)or(N%2==1):
      if o[0]>even[k+1][0]:
        tmp = False
        break
    
    ind[2*k]=e[1]
    ind[2*k+1]=o[1]

  if tmp:
    if N%2==1:
      ind[N-1]=even[-1][1]
      

    for k in range(N):
      y = ind[k]
      x+=abs(y-k)
      ind = [x+1 if (x<y)and(x>=k) else x for x in ind]
    ans = min(ans,x)
    judge = True
    
if judge:
  print(ans)
else:
  print(-1)

Solution (Python):














import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

class BinaryIndexedTree():
    def __init__(self, size):
        self.__node=[0]*(size+1)
        self.size = size

    
    def add(self, index, value):
        while index <= self.size:
            self.__node[index] += value
            index += index&-index    
    
    
    def sum(self, index):
        ret = 0 
        while index > 0:
            ret += self.__node[index]
            index -= index&-index    
        return ret

    def update_max(self, index, value):
        while index <= self.size:
            self.__node[index] = max(self.__node[index], value)
            index += index & -index


    
    def query_max(self, index):
        ret = 0
        while index > 0:
            ret = max(ret, self.__node[index])
            index -= index & -index
        return ret
        
        

    
    def get_node(self, index):
        return self.__node[index]
def Inversion_number(A):
    N=len(A)
    B=sorted(set(A))
    BIT = BinaryIndexedTree(N)
    res = 0
    for i in range(N):
        idx = bisect_left(B,A[i])
        inverse = i - BIT.sum(idx+1)
        res += inverse
        BIT.add(idx+1,1)
    return res

def main():
    N=I()
    A=LI()
    B=LI()
    max_bit = 1<<N


        
    def check(mask): 
        """
        ビットが立ってるところは裏
        裏になるものは元いる位置から奇数移動
        表になるものは元いる位置から偶数移動
        """
        C=[0]*N
        for i in range(N):
            if (mask>>i&1):
                C[i] = B[i]
            else:
                C[i] = A[i]

        C.sort()
        dic = defaultdict(lambda : deque())
        for j,c in enumerate(C):
            dic[c,j&1].append(j)
        
        indexes = [0]*N
        for i in range(N):
            if (mask>>i&1):
                num,is_odd_idx = (B[i],i&1)
                if dic[num,is_odd_idx^1]:
                    idx = dic[num,is_odd_idx^1].popleft()
                else:
                    return inf
            else:
                num,is_odd_idx = A[i],i&1
                if dic[num,is_odd_idx]:
                    idx = dic[num,is_odd_idx].popleft()
                else:
                    return inf
            indexes[i] = idx

        return Inversion_number(indexes)


    ans = inf
    for mask in range(max_bit):
        res = check(mask)
        if res < ans:
            ans = res
    if ans == inf:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def tentousu(a):
  ans=0
  for i in range(len(a)):
    for j in range(i+1,len(a)):
      if a[i]>a[j]:ans+=1
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  if s.count("0")!=n//2:continue
  ac=[]
  bc=[]
  for j in range(n):
    if s[j]=="1":ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Solution (Python):
def tentousu(a):
  ans=0
  for i in range(len(a)):
    for j in range(i+1,len(a)):
      if a[i]>a[j]:ans+=1
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  if s.count("0")!=n//2:continue
  if s.count("1")!=n//2 and s.count("1")!=n//2+1:continue
  ac=[]
  bc=[]
  for j in range(n):
    if s[j]=="1":ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Solution (Python):
def tentousu(a):
  ans=0
  for i in range(len(a)):
    for j in range(i+1,len(a)):
      if a[i]>a[j]:ans+=1
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  if s.count("0")!=n//2:continue
  ac=[]
  bc=[]
  for j in range(n):
    if s[j]=="1":ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Solution (Python):
class BinaryIndexedTree():
  def __init__(self,n):self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_1(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_1(j-1)
    if i!=0:a-=self.sum_1(i-1)
    return a
def tentousu(a):
  bit=BinaryIndexedTree(n)
  b=[0]*n
  for i in range(n):
    b[a[i]]=i
  ans=0
  for i in range(n):
    j=b[i]+bit.sum(b[i]+1,n)
    ans+=j-i
    bit.add(b[i],1)
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  if s.count("0")!=n//2:continue
  ac=[]
  bc=[]
  for j in range(n):
    if s[j]=="1":ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

Solution (Python):
from collections import defaultdict
from operator import itemgetter
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 1000
for n in range(2**N):
    n = bin(n)[2:]
    if n.count('1')%2!=0:
        continue
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i])
        else:
            l.append([B[i],i+1])
    inversion = 0
    for i in range(N):
        if inversion>=ans:
            break
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    if inversion>=ans:
        continue
    l.sort(key=itemgetter(0))
    d = defaultdict(list)
    for i in range(N):
        v,j = l[i]
        if (i-j)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

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

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def f(n):
    count=0
    while n:
        count+=n%2
        n//=2
    return count

n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
for bit in range(2**n):
    
    
    arr=[]
    for i in range(n):
        if bit >> i & 1:
            arr.append((B[i],i))
        else:
            arr.append((A[i],i))
    i=0;flug=1;tmp=0
    while flug:
        flug=0
        for j in range(n-1,i,-1):
            if arr[j-1][0]>arr[j][0]:
                arr[j-1],arr[j]=arr[j],arr[j-1]
                tmp+=1; flug=1
        i+=1
    stack=[]
    for i in range(n):
        if (abs(arr[i][1]-i)) % 2 != bit >> arr[i][1] & 1:
            stack.append(arr[i][0]*1000+i)
    
        
        
    if len(stack) & 1:
        tmp=1000; stack.pop()
    while stack:
        p=stack.pop(); q=stack.pop()
        if (p-q) & 1:
            tmp+=p-q
            
                
                
        else:
            tmp+=1000
    mans=min(mans,tmp)

print(-1 if mans > 999 else mans)

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]

ans = 1 << 100
for m in range(1<<N):
    b = bin(m)
    if b[::2].count("1") != b[1::2].count("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]
        t = 0
        for i in range(N):
            for j in range(i):
                if CCC[i] < CCC[j]: t += 1
        ans = min(ans, t)
print(ans if ans < 1 << 100 else -1)

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):
    b = bin(m)
    if b[::2].count("1") != b[1::2].count("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):
from itertools import combinations

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):
    seq = [i + 1 for i in 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

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









ptn = list(combinations(range(N), N//2))

ans = - 1
for p in ptn:
  evnline = []
  oddline = []
  for i in range(N):
    if i in p:
      evnline.append((A[i] if (i + 1) % 2 == 0 else B[i], i))
    else:
      oddline.append((B[i] if (i + 1) % 2 == 0 else A[i], i))
  line = [0] * N
  evnline.sort()
  oddline.sort()

  for itr, val in enumerate(evnline):
    line[itr * 2 + 1] = val
  for itr, val in enumerate(oddline):
    line[itr * 2] = val
  if all([j[0] >= i[0] for i, j in zip(line,line[1:])]):
    exchange_cnt = Inversion([i[1] for i in line])
    if ans == -1:
      ans = exchange_cnt
    else:
      ans = min(ans, exchange_cnt)

print(ans)

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

INF = 1 << 20
dp = [[INF] * 51 for _ in range(1 << N)]
dp[0][0] = 0

for bit in range(1 << N):
    
    con = bin(bit).count("1")

    
    ords = []
    iters = con
    for i in range(N):
        if not (bit & (1 << i)):
            ords.append([i, iters])
            iters += 1

    for s in range(51):
        if dp[bit][s] >= INF:
            continue

        for p in ords:
            
            
            
            ns = A[p[0]] if abs(p[0] - con) % 2 == 0 else B[p[0]]

            
            
            
            if ns >= s:
                
                dp[bit|(1 << p[0])][ns] = min(dp[bit|(1 << p[0])][ns],
                                              dp[bit][s] + abs(con - p[1]))

ans = min(dp[-1][s] for s in range(51))
print(ans if ans < INF else -1)

Solution (Python):
import sys
import itertools
INF = float("INF")

N = int(input())
AA = list(map(int, sys.stdin.readline().split()))
BB = list(map(int, sys.stdin.readline().split()))

cards = set()
for i,(a,b) in enumerate(zip(AA,BB)):
    if i%2 == 0:
        cards.add((a, b, i))
    else:
        cards.add((b, a, i))

def solve(ii):
    tmp = 0
    for i in range(N):
        for j in range(i+1,N):
            if ii[i] > ii[j]:
                tmp += 1
    return tmp

ans = INF
for Acards in itertools.combinations(cards, (N+1)//2):
    Bcards = cards - set(Acards)

    Ais = sorted([(card[0], card[2]) for card in Acards])
    Bis = sorted([(card[1], card[2]) for card in Bcards])

    bn = -1
    ii = []
    flag = False
    for i in range(N):
        if i%2 == 0:
            n,i = Ais[i//2]
        else:
            n,i = Bis[i//2]
        if bn > n: 
            flag = True
            break
        bn = n
        ii.append(i)

    if flag: continue

    ans = min(ans,solve(ii))


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

Solution (Python):
import sys
import itertools
INF = float("INF")

N = int(input())
AA = list(map(int, sys.stdin.readline().split()))
BB = list(map(int, sys.stdin.readline().split()))

cards = set()
for i,(a,b) in enumerate(zip(AA,BB)):
    if i%2 == 0:
        cards.add((a, b, i))
    else:
        cards.add((b, a, i))

def solve(ii):
    tmp = 0
    for i in range(N):
        for j in range(i+1,N):
            if ii[i] > ii[j]:
                tmp += 1
    return tmp

ans = INF
for Acards in itertools.combinations(cards, (N+1)//2):
    Bcards = cards - set(Acards)

    Ais = sorted([(card[0], card[2]) for card in Acards])
    Bis = sorted([(card[1], card[2]) for card in Bcards])

    bn = -1
    ii = []
    flag = False
    for i in range(N):
        if i%2 == 0:
            n,i = Ais[i//2]
        else:
            n,i = Bis[i//2]
        if bn > n: 
            flag = True
            break
        bn = n
        ii.append(i)

    if flag: continue

    ans = min(ans,solve(ii))


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

Solution (Python):





import sys
import itertools
INF = float("INF")

N = int(input())
AA = list(map(int, sys.stdin.readline().split()))
BB = list(map(int, sys.stdin.readline().split()))

cards = set()
for i,(a,b) in enumerate(zip(AA,BB)):
    if i%2 == 0:
        cards.add((a, b, i))
    else:
        cards.add((b, a, i))

def solve(ii):
    tmp = 0
    for i in range(N):
        for j in range(i+1,N):
            if ii[i] > ii[j]:
                tmp += 1
    return tmp

ans = INF
for Acards in itertools.combinations(cards, (N+1)//2):
    Bcards = cards - set(Acards)

    Ais = sorted([(card[0], card[2]) for card in Acards])
    Bis = sorted([(card[1], card[2]) for card in Bcards])

    bn = -1
    ii = []
    flag = False
    for i in range(N):
        if i%2 == 0:
            n,i = Ais[i//2]
        else:
            n,i = Bis[i//2]
        if bn > n:
            flag = True
        bn = n
        ii.append(i)

    if flag: continue

    ans = min(ans,solve(ii))


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