CodeEff/ECCO huggingface dataset:
# Original solution
def main():
  N = int(eval(input()))
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  # M:カードの数字の最大値+1
  M = max(max(A),max(B))+1
  INF=float('inf')
  # dp[mask][a]:maskのカードが操作済で、そのうち右端のカードの数字がaであるときの操作回数の最小値
  dp = [[INF for _ in range(M)] for _ in range(1<<N)]
  dp[0][0] = 0
  
  for i in range(1<<N):
    # idx:操作済カードの枚数
    idx = 0
    for k in range(N):
      #k番目のカードが操作済みかどうか判定する。iでk番目にフラグがたってたら、操作済みとする。
      if (i>>k)&1 == 1:
        idx += 1
    for j in range(M):
      if dp[i][j] >= INF:
        continue
      for k in range(N):
        # k:右端の操作済カードの次に来るカード
        # kがすでに操作済の場合はcontinueする
        if (i>>k)&1:
          continue
        
        # kが何回操作されるかによってkの数字が表の数字になるか裏の数字になるかが決まる
        if abs(k-idx)%2 == 0:
          c = A[k]
        else:
          c = B[k]
  
        # kの数字広義単調増加にならない場合はcontinue
        if j > c:
          continue
        
        # t:kを右端の操作済カードの次に並べるための操作回数
        # それは、初期配置でkより左にあってまだ操作済でないカードの枚数と一致する
        t = 0
        for l in range(k):
          if (i>>l)&1 == 0:
            t += 1
        #print(i,k,idx,c,dp[i|(1<<k)][c],t)
        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()

# Optimized solution
N = int(eval(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)
# Original solution
# from collections import defaultdict,deque
# import sys,heapq,bisect,math,itertools,string,queue,copy,time
# sys.setrecursionlimit(10**8)
#
#
import sys
import itertools
INF = float("INF")

N = int(eval(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 _ in range(N):
        next = []
        for k, i in enumerate(ii):
            if i == 0:
                tmp += k
            else:
                next.append(i-1)
        ii = next[:]
    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)


# Optimized solution
# from collections import defaultdict,deque
# import sys,heapq,bisect,math,itertools,string,queue,copy,time
# sys.setrecursionlimit(10**8)
#
#
import sys
import itertools
INF = float("INF")

N = int(eval(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)
# Original solution
import sys
from itertools import combinations
input = sys.stdin.readline
n = int(eval(input()))
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]

all_cards = []
for i, (aa, bb) in enumerate(zip(a, b)):
    all_cards.append((aa, bb, i))

def check(cards):
    pre = -1
    for c in cards:
        print(c)
        if c[0] >= pre:
            pre = c[0]
        else:
            return False
    else:
        return True

def cnt(l):
    ret = 0
    for i in range(len(l)-1):
        for j in range(i+1, len(l)):
            if l[i] > l[j]:
                ret += 1
    return ret

def dp(all_cards, l, p):
    i = len(l) + 1
    if len(l) == n:
        return cnt(l)
    ret = float('inf')
    for card in all_cards:
        if card[2] not in l and card[0] < p and card[1] < p:
            return ret
    for card in all_cards:
        if card[2] in l:
            continue
        if card[(i-(card[2]+1))%2] >= p:
            ret = min(ret, dp(all_cards - set(card), l+[card[2]], card[(i-(card[2]+1))%2]))
    return ret

ans = dp(set(all_cards), [], -float('inf'))
if ans == float('inf'):
    ans = -1
print(ans)

# Optimized solution
import sys
from itertools import combinations
input = sys.stdin.readline
n = int(eval(input()))
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]

all_cards = []
for i, (aa, bb) in enumerate(zip(a, b)):
    if i % 2:
        aa, bb = bb, aa
    all_cards.append([aa, bb, i])

def cnt(l):
    ret = 0
    for i in range(len(l)-1):
        for j in range(i+1, len(l)):
            if l[i][1] > l[j][1]:
                ret += 1
    return ret

ans = float('inf')
for cards in combinations(all_cards, (n + 1)// 2):
    acards = []
    for card in cards:
        acards.append([card[0],card[2]])
    bcards = []
    for card in all_cards:
        if [card[0],card[2]] not in acards:
            bcards.append([card[1],card[2]])

    acards.sort()
    bcards.sort()
    abcards = []
    # print(acards, bcards)
    for i in range(len(bcards)):
        abcards.extend([acards[i], bcards[i]])
    else:
        if n % 2:
            abcards.append(acards[-1])
    # print(abcards)
    if abcards != sorted(abcards, key=lambda x: x[0]):
        continue
    ans = min(ans, cnt(abcards))

if ans == float('inf'):
    ans = -1
print(ans)
# Original solution
n=int(eval(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))


# Optimized solution
n=int(eval(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))
# Original solution
from collections import defaultdict

n = int(eval(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

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 list(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]
                nxt[to][nstate] = min(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)

# Optimized solution
from collections import defaultdict

def main():

    n = int(eval(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 list(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()
# Original solution
N = int(eval(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))

# Optimized solution
N = int(eval(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))
# Original solution
n = int(eval(input()))
a = [list(map(int,input().split())) for _ in range(2)]
dp = [[1000]*(2**n) for _ in range(51)]
dp[0][0] = 0
for S in range(2**n):
  j = bin(S).count("1")
  for i in range(n):
    if not (S & 1<<i):
      cnt = bin(S)[2:].zfill(n)[n-i:].count("0")
      k = a[(i+j)%2][i]
      for l in range(k+1):
        dp[k][S|1<<i] = min(dp[k][S|1<<i],dp[l][S]+cnt)
ans = min(dp[i][-1] for i in range(51))
if ans == 1000:
  print((-1))
else:
  print(ans)

# Optimized solution
n = int(eval(input()))
a = [list(map(int,input().split())) for _ in range(2)]
dp = [[1000]*(2**n) for _ in range(51)]
dp[0][0] = 0
for S in range(2**n):
  j = bin(S).count("1")
  cnt = 0
  for i in range(n):
    if not (S & 1<<i):
      k = a[(i+j)%2][i]
      for l in range(k+1):
        dp[k][S|1<<i] = min(dp[k][S|1<<i],dp[l][S]+cnt)
    if not (S&1<<i):
      cnt += 1
ans = min(dp[i][-1] for i in range(51))
if ans == 1000:
  print((-1))
else:
  print(ans)
# Original solution
from itertools import permutations
n = int(eval(input()))
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

c = []
for i in range(n):
    c.append((a[i], b[i]))


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 bubcnt(v):
    bit = Bit(n)
    kaisu = 0
    for i in range(0, n):
        kaisu += i - bit.sum(v[i])
        bit.add(v[i], 1)
    return kaisu


l = [i+1 for i in range(n)]
ans = 10**9

xxx = permutations(l,n)

for v in xxx:
    tmp = 0
    cnt = 0
    for i in range(n):
        if tmp <= c[v[i]-1][(i-v[i]+1) % 2]:
            tmp = c[v[i]-1][(i-v[i]+1) % 2]
            cnt += 1
        else:
            break
    if cnt == n:
        ans = min(ans, bubcnt(v))

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


# Optimized solution
n = int(eval(input()))
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

dp = [[10**9 for _ in range(51)] for __ in range(1 << n)]
dp[0][0] = 0


for i in range(1 << n):
    target = bin(i).count("1")-1
    cnt = bin(i).count("1")
    for j in range(n):
        if i >> j & 1:
            cnt -= 1
            if abs(j - target) % 2 == 0:
                nxt = a[j]
            else:
                nxt = b[j]
            for k in range(nxt+1):
                if dp[i ^ (1 << j)][k] != 10**9:
                    dp[i][nxt] = min(dp[i][nxt], dp[i ^ (1 << j)][k] + abs(j+cnt-target))

ans = min(dp[2**n-1])

print((ans if ans < 10**9 else -1))
# Original solution
import itertools
n=int(eval(input()))
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**n:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

def tentou(X):
  ret=0
  BIT=[0]*nn
  BIT.insert(0,0)
  for i1 in range(n):
    x=X[i1]+1
    ret+=i1-bitsum(BIT,x)
    bitadd(BIT,x,1)
  return ret
N=[int(i) for i in range(n)]
nn=2**n
ans=float("inf")
for _ in range(n//2+1):
  for com in itertools.combinations(N,2*_):
    E,O=[],[]
    for j in range(n):
      if j not in com:
        if j%2==0:
          E.append(A[j]*100+j)
        else:
          O.append(A[j]*100+j)
      else:
        if j%2==0:
          O.append(B[j]*100+j)
        else:
          E.append(B[j]*100+j)
    if len(E)!=(n+1)//2:
      continue
    else:
      E.sort()
      O.sort()

      chk=True
      C=[E[0]%100]
      prev=E[0]//100
      for i in range(1,n):
        ii=i//2
        if i%2==0:
          C.append(E[ii]%100)
          if E[ii]//100<prev:
            chk=False
            break
          else:
            prev=E[ii]//100
        else:
          C.append(O[ii]%100)
          if O[ii]//100<prev:
            chk=False
            break
          else:
            prev=O[ii]//100
    
    if chk:
      ans=min(ans,tentou(C))
print((-1 if ans==float("inf") else ans))



# Optimized solution
import itertools
n=int(eval(input()))
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=64:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

def tentou(X):
  ret=0
  BIT=[0]*64
  BIT.insert(0,0)
  for i1 in range(n):
    x=X[i1]+1
    ret+=i1-bitsum(BIT,x)
    bitadd(BIT,x,1)
  return ret
N=[int(i) for i in range(n)]
nn=2**n
ans=float("inf")
for _ in range(n//2+1):
  for com in itertools.combinations(N,2*_):
    i=0
    for ura in com:
      i+=2**ura
    E,O=[],[]
    for j in range(n):
      if i&(1<<j)==0:
        if j%2==0:
          E.append(A[j]*100+j)
        else:
          O.append(A[j]*100+j)
      else:
        if j%2==0:
          O.append(B[j]*100+j)
        else:
          E.append(B[j]*100+j)
    if len(E)!=(n+1)//2:
      continue
    else:
      E.sort()
      O.sort()

      chk=True
      C=[E[0]%100]
      prev=E[0]//100
      for i in range(1,n):
        ii=i//2
        if i%2==0:
          C.append(E[ii]%100)
          if E[ii]//100<prev:
            chk=False
            break
          else:
            prev=E[ii]//100
        else:
          C.append(O[ii]%100)
          if O[ii]//100<prev:
            chk=False
            break
          else:
            prev=O[ii]//100
    
    if chk:
      ans=min(ans,tentou(C))
print((-1 if ans==float("inf") else ans))
# Original solution
import itertools
n=int(eval(input()))
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=64:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

def tentou(X):
  ret=0
  BIT=[0]*64
  BIT.insert(0,0)
  for i1 in range(n):
    x=X[i1]+1
    ret+=i1-bitsum(BIT,x)
    bitadd(BIT,x,1)
  return ret
N=[int(i) for i in range(n)]
nn=2**n
ans=float("inf")
for _ in range(n//2+1):
  for com in itertools.combinations(N,2*_):
    i=0
    for ura in com:
      i+=2**ura
    E,O=[],[]
    for j in range(n):
      if i&(1<<j)==0:
        if j%2==0:
          E.append(A[j]*100+j)
        else:
          O.append(A[j]*100+j)
      else:
        if j%2==0:
          O.append(B[j]*100+j)
        else:
          E.append(B[j]*100+j)
    if len(E)!=(n+1)//2:
      continue
    else:
      E.sort()
      O.sort()

      chk=True
      C=[E[0]%100]
      prev=E[0]//100
      for i in range(1,n):
        ii=i//2
        if i%2==0:
          C.append(E[ii]%100)
          if E[ii]//100<prev:
            chk=False
            break
          else:
            prev=E[ii]//100
        else:
          C.append(O[ii]%100)
          if O[ii]//100<prev:
            chk=False
            break
          else:
            prev=O[ii]//100
    
    if chk:
      ans=min(ans,tentou(C))
print((-1 if ans==float("inf") else ans))



# Optimized solution
import itertools
n=int(eval(input()))
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

N=[int(i) for i in range(n)]
nn=2**n
ans=float("inf")
for _ in range(n//2+1):
  for com in itertools.combinations(N,2*_):
    i=0
    for ura in com:
      i+=2**ura
    E,O=[],[]
    for j in range(n):
      if i&(1<<j)==0:
        if j%2==0:
          E.append(A[j]*100+j)
        else:
          O.append(A[j]*100+j)
      else:
        if j%2==0:
          O.append(B[j]*100+j)
        else:
          E.append(B[j]*100+j)
    if len(E)!=(n+1)//2:
      continue
    else:
      E.sort()
      O.sort()

      chk=True
      C=[E[0]%100]
      prev=E[0]//100
      for i in range(1,n):
        ii=i//2
        if i%2==0:
          C.append(E[ii]%100)
          if E[ii]//100<prev:
            chk=False
            break
          else:
            prev=E[ii]//100
        else:
          C.append(O[ii]%100)
          if O[ii]//100<prev:
            chk=False
            break
          else:
            prev=O[ii]//100
    
    if chk:
      ten=0
      for i1 in range(n):
        for i2 in range(i1+1,n):
          if C[i1]>C[i2]:
            ten+=1
      ans=min(ans,ten)
print((-1 if ans==float("inf") else ans))
# Original solution
import sys
stdin = sys.stdin

ni = lambda: int(ns)
ns = lambda: stdin.readline().rstrip()
na = lambda: map(int, stdin.readline().split())

from itertools import groupby

def f(x):
  groups = []
  for _, g in groupby(x):
    groups += [list(g)]
 
  ans = 0
  flag = False
  for group in groups:
    n = len(group)
    if flag:
      n -= 1
      flag = False
    if n == 0:
      print(group, file=sys.stderr)
      continue
    c = (n-1)//3 * 2
    o = n%3
    if o == 0:
      d = 2
    elif o == 1:
      d = 1
    elif o == 2:
      d = 2
      flag = True
    print(group, c, d, file=sys.stderr)
    ans += c + d
  if flag:
    ans -= 1
  print(ans, file=sys.stderr)
  return ans

def solve():
  s = ns()
  print(max(f(s), f(s[::-1])))


if __name__ == '__main__':
  solve()


# Optimized solution
import sys
from itertools import groupby

def f(x):
  groups = []
  for _, g in groupby(x):
    groups += [list(g)]
 
  ans = 0
  flag = False
  for group in groups:
    n = len(group)
    if flag:
      n -= 1
      flag = False
    if n == 0:
      print(group, file=sys.stderr)
      continue
    c = (n-1)//3 * 2
    o = n%3
    if o == 0:
      d = 2
    elif o == 1:
      d = 1
    elif o == 2:
      d = 2
      flag = True
    print(group, c, d, file=sys.stderr)
    ans += c + d
  if flag:
    ans -= 1
  print(ans, file=sys.stderr)
  return ans

def solve():
  s = input()
  print(f(s))


if __name__ == '__main__':
  solve()