Problem:
 Score : 600 points    Problem Statement There are 2N balls, N white and N black, arranged in a row. The integers from 1 through N are written on the white balls, one on each ball, and they are also written on the black balls, one on each ball.
The integer written on the i -th ball from the left ( 1  ≤  i  ≤  2N ) is a_i , and the color of this ball is represented by a letter c_i . c_i  =  W represents the ball is white; c_i  =  B represents the ball is black.  Takahashi the human wants to achieve the following objective:   For every pair of integers (i,j) such that 1  ≤  i  <  j  ≤  N , the white ball with i written on it is to the left of the white ball with j written on it.  For every pair of integers (i,j) such that 1  ≤  i  <  j  ≤  N , the black ball with i written on it is to the left of the black ball with j written on it.   In order to achieve this, he can perform the following operation:   Swap two adjacent balls.   Find the minimum number of operations required to achieve the objective.      Constraints  1  ≤  N  ≤  2000  1  ≤  a_i  ≤  N  c_i  =  W or c_i  =  B .  If i  ≠  j , (a_i,c_i)  ≠  (a_j,c_j) .         Input Input is given from Standard Input in the following format:  N  c_1  a_1  c_2  a_2  :  c_{2N}  a_{2N}       Output Print the minimum number of operations required to achieve the objective.        Sample Input 1 3
B 1
W 2
B 3
W 1
W 3
B 2      Sample Output 1 4  The objective can be achieved in four operations, for example, as follows:   Swap the black 3 and white 1 .  Swap the white 1 and white 2 .  Swap the black 3 and white 3 .  Swap the black 3 and black 2 .        Sample Input 2 4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1      Sample Output 2 18       Sample Input 3 9
W 3
B 1
B 4
W 1
B 5
W 9
W 2
B 6
W 5
B 3
W 8
B 9
W 7
B 2
B 8
W 4
W 6
B 7      Sample Output 3 41

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

N = int(input())
c = [0] * (2 * N)
a = [0] * (2 * N)
for i in range(2 * N):
    c[i], a[i] = input().split()
    a[i] = int(a[i]) - 1

idx = [[0] * 2 for _ in range(N)]
for i in range(2 * N):
    idx[a[i]][c[i] == 'W'] = i

costB = [[0] * (N + 1) for _ in range(N)]
for i in range(N):
    j = idx[i][0]
    cnt = 0
    for k in range(i):
        if j < idx[k][0]:
            cnt += 1
    costB[i][0] = j + cnt - i
    cnt2 = 0
    for k in range(1, N + 1):
        if j < idx[k - 1][1]:
            cnt2 += 1
        costB[i][k] = j + cnt + cnt2 - (i + k)

costW = [[0] * (N + 1) for _ in range(N)]
for i in range(N):
    j = idx[i][1]
    cnt = 0
    for k in range(i):
        if j < idx[k][1]:
            cnt += 1
    costW[i][0] = j + cnt - i
    cnt2 = 0
    for k in range(1, N + 1):
        if j < idx[k - 1][0]:
            cnt2 += 1
        costW[i][k] = j + cnt + cnt2 - (i + k)

dp = [[10**18] * (N + 1) for _ in range(2 * N + 1)]
dp[0][0] = 0
for i in range(1, 2 * N + 1):
    for j in range(max(0, i - N), min(i, N) + 1):
        dp[i][j] = dp[i-1][j] + costW[i-j-1][j]
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j-1] + costB[j-1][i-j])
print(dp[2*N][N])

Solution (Python):
def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return


def examE():
    N = I()
    Bnum = [-1]*N
    Wnum = [-1]*N
    B = {}
    W = {}
    for i in range(2*N):
        c, a = LSI()
        a = int(a)-1
        if c=="W":
            W[i] = a+1
            Wnum[a] = i
        else:
            B[i] = a+1
            Bnum[a] = i
    SB = [[0]*(N*2) for _ in range(N+1)]; SW = [[0]*(N*2) for _ in range(N+1)]
    for i in range(2*N):
        if not i in B:
            continue
        cur = B[i]
        cnt = 0
        SB[cur][i] = 0
        for j in range(2*N):
            if not j in B:
                SB[cur][j] = cnt
                continue
            if B[j]<=cur:
                cnt += 1
            SB[cur][j] = cnt
    for i in range(2*N):
        if not i in W:
            continue
        cur = W[i]
        cnt = 0
        SW[cur][i] = 0
        for j in range(2*N):
            if not j in W:
                SW[cur][j] = cnt
                continue
            if W[j]<=cur:
                cnt += 1
            SW[cur][j] = cnt
    
        
    
    

    dp = [[inf]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        dp[0][i+1] = dp[0][i]+Bnum[i]-SB[i][Bnum[i]]
        dp[i+1][0] = dp[i][0]+Wnum[i]-SW[i][Wnum[i]]
    
    for i in range(N):
        w = Wnum[i]
        for j in range(N):
            b = Bnum[j]
            costb = b - (SB[j][b]+SW[i+1][b])
            costw = w - (SB[j+1][w]+SW[i][w])
            
            
            
            
            
            if costb<0:
                costb = 0
                
            if costw < 0:
                costw = 0
                
            dp[i+1][j+1] = min(dp[i+1][j+1],dp[i+1][j]+costb,dp[i][j+1]+costw)
    ans = dp[-1][-1]
    
    
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a == "B", int(b)-1) for a, b in ab]
    dct_b = [0]*n
    dct_w = [0]*n
    for i, (a, b) in enumerate(ab):
        if a:
            dct_b[b] = i
        else:
            dct_w[b] = i

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  
    dp[0][0] = 0

    
    lb = [[0]*(n+1) for _ in [0]*(2*n)]
    lw = [[0]*(n+1) for _ in [0]*(2*n)]

    for j in range(n):
        cnt1, cnt2 = 0, 0
        for i, (a, b) in enumerate(ab):
            lb[i][j] = cnt1
            lw[i][j] = cnt2
            if a:
                if b >= j:
                    cnt1 += 1
            else:
                if b >= j:
                    cnt2 += 1

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  
    dp[0][0] = 0

    for i in range(n+1):
        dp1 = dp[i]
        if i < n:
            dp2 = dp[i+1]
            t = dct_b[i]
        for j in range(n+1):
            d = dp1[j]
            if i < n:
                dp2[j] = min(dp2[j], d+lb[t][i]+lw[t][j])
            if j < n:
                t2 = dct_w[j]
                dp1[j+1] = min(dp1[j+1], d+lb[t2][i]+lw[t2][j])
    print(dp[n][n])


main()

Solution (Python):
N=int(input())
dic={"B":[0]*N,"W":[0]*N}
for i in range(2*N):
    c,a=input().split()
    a=int(a)
    dic[c][a-1]=i

Btable=[[0 for i in range(N+1)] for i in range(N)]
BBtable=[0 for i in range(N)]
S=0
for i in range(1,N):
    S=0
    for j in range(0,i):
        S+=(dic["B"][i]<dic["B"][j])
    BBtable[i]=S

for i in range(N):
    S=0
    for j in range(1,N+1):
        if dic["W"][j-1]>dic["B"][i]:
            S+=1
        Btable[i][j]=S+BBtable[i]
    Btable[i][0]=BBtable[i]

Wtable=[[0 for i in range(N+1)] for i in range(N)]
WWtable=[0 for i in range(N)]
S=0
for i in range(1,N):
    S=0
    for j in range(0,i):
        S+=(dic["W"][i]<dic["W"][j])
    WWtable[i]=S

for i in range(N):
    S=0
    for j in range(1,N+1):
        if dic["B"][j-1]>dic["W"][i]:
            S+=1
        Wtable[i][j]=S+WWtable[i]
    Wtable[i][0]=WWtable[i]

dp=[[0 for j in range(N+1)] for i in range(N+1)]

for j in range(N-1,-1,-1):
    dp[N][j]=dp[N][j+1]+Wtable[j][N]

for i in range(N-1,-1,-1):
    for j in range(N,-1,-1):
        if j!=N:
            dp[i][j]=min(dp[i+1][j]+Btable[i][j],dp[i][j+1]+Wtable[j][i])
        else:
            dp[i][j]=dp[i+1][j]+Btable[i][j]


print(dp[0][0])

Solution (Python):
n=int(input())
b=[0]*n
w=[0]*n
for i in range(2*n):
  c,a=input().split()
  if c=="B":b[int(a)-1]=i
  else:w[int(a)-1]=i
bit=[0]*2*n
dp=[(n+1)*[10**10]for _ in range(n+1)]
dp[0][0]=0
for i in range(n+1):
  bitt=bit[:]
  for j in range(n):
    a=0
    k=2*n
    while k:
      a+=bitt[k-1]
      k-=k&-k
    if w[j]!=0:
      k=w[j]
      while k:
        a-=bitt[k-1]
        k-=k&-k
    dp[i][j+1]=min(dp[i][j+1],dp[i][j]+a+w[j]-(i+j))
    k=w[j]+1
    while k<=2*n:
      bitt[k-1]+=1
      k+=k&-k
    if i!=n:
      a=0
      k=2*n
      while k:
        a+=bitt[k-1]
        k-=k&-k
      if b[i]!=0:
        k=b[i]
        while k:
          a-=bitt[k-1]
          k-=k&-k
      dp[i+1][j+1]=dp[i][j+1]+a+b[i]-(i+j+1)
  if i!=n:
    a=b[i]-i
    k=2*n
    while k:
      a+=bit[k-1]
      k-=k&-k
    if b[i]!=0:
      k=b[i]
      while k:
        a-=bit[k-1]
        k-=k&-k
    dp[i+1][0]=dp[i][0]+a
    k=b[i]+1
    while k<=2*n:
      bit[k-1]+=1
      k+=k&-k
print(dp[n][n])

Solution (Python):
N=int(input())
Ball=[]
for i in range(2*N):
  c,a=input().split()
  Ball.append((c,int(a)))
B=[0]*N
W=[0]*N
B_table=[[0]*(N+1) for i in range(N)]
W_table=[[0]*(N+1) for i in range(N)]
for i in range(2*N):
  c=Ball[i][1]-1
  if Ball[i][0]=="B":
    B[c]=i+1
    for j in range(i+1,2*N):
      if Ball[j][0]=="B":
        if Ball[j][1]<Ball[i][1]:
          B_table[Ball[i][1]-1][0]+=1
      elif Ball[j][0]=="W":
        B_table[c][Ball[j][1]]+=1
    for k in range(N):
      B_table[c][k+1]+=B_table[c][k]
  elif Ball[i][0]=="W":
    W[c]=i+1
    for j in range(i+1,2*N):
      if Ball[j][0]=="W":
        if Ball[j][1]<Ball[i][1]:
          W_table[c][0]+=1
      elif Ball[j][0]=="B":
        W_table[c][Ball[j][1]]+=1
    for k in range(N):
      W_table[c][k+1]+=W_table[c][k]
dp=[[0]*(N+1) for i in range(N+1)]
for s in range(1,2*N+1):
  for b in range(max(0,s-N),min(s,N)+1):
    if b==0:
      dp[0][s]=dp[0][s-1]+(W[s-1]+W_table[s-1][0]-s)
    elif b==s:
      dp[s][0]=dp[s-1][0]+(B[s-1]+B_table[s-1][0]-s)
    else:
      dp[b][s-b]=min(dp[b-1][s-b]+(B[b-1]+B_table[b-1][s-b]-s),dp[b][s-b-1]+(W[s-b-1]+W_table[s-b-1][b]-s))
print(dp[N][N])

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


n = int(input())
INF = 10 ** 9
info = [list(input().split()) for i in range(2 * n)]

ind = {}
for i in range(2 * n):
    if info[i][0] == "B":
        info[i] = (0, int(info[i][1]))
    else:
        info[i] = (1, int(info[i][1]))
    ind[info[i][0] * 10 ** 5 + info[i][1]] = i

ru_b = [[0] * (2 * n + 1) for i in range(n + 1)]
ru_w = [[0] * (2 * n + 1) for i in range(n + 1)]
for i in range(n + 1):
    for j in range(2 * n):
        col, num = info[j]
        if col == 0 and num > i:
            ru_b[i][j + 1] += 1
        elif col == 1 and num > i:
            ru_w[i][j + 1] += 1
    for j in range(2 * n):
        ru_b[i][j + 1] += ru_b[i][j]
        ru_w[i][j + 1] += ru_w[i][j]    


dp = [[INF] * (n + 1) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n + 1):
    for j in range(n + 1):
        if i + 1 <= n and j <= n:
            bi = ind[i + 1]
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + ru_b[i][bi] + ru_w[j][bi])
        if i <= n and j + 1 <= n:
            wi = ind[10 ** 5 + j + 1]
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + ru_w[j][wi] + ru_b[i][wi])

print(dp[-1][-1])

Solution (Python):
N = int(input())
X = [i for i in range(N+1)]
Y = [[] for _ in range(N)]
B, W = [], []
ans = 0
for i in range(2 * N):
    c, a = input().split()
    a = int(a) - 1
    if c == "B":
        X = [X[i] + 1 if i <= a else X[i] - 1 for i in range(N+1)]
        B.append(a)
        ans += len([b for b in B if b > a])
    else:
        Y[a] = X[:]
        W.append(a)
        ans += len([b for b in W if b > a])

Z = [0] * (N+1)
for y in Y:
    for i in range(N+1):
        Z[i] += y[i]
    for i in range(1, N+1):
        Z[i] = min(Z[i], Z[i-1])

ans += Z[-1]
print(ans)

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7




def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret



N = int(sys.stdin.buffer.readline())
CA = [sys.stdin.buffer.readline().decode().rstrip().split() for _ in range(N * 2)]
C = []
A = []
for c, a in CA:
    C.append(c)
    A.append(int(a))

pos_w = [IINF] * (N + 1)
pos_b = [IINF] * (N + 1)
for i, (c, a) in enumerate(list(zip(C, A))):
    if c == 'W':
        pos_w[a] = i
    else:
        pos_b[a] = i



bc = [0] * (N * 2 + 1)
wc = [0] * (N * 2 + 1)
count_b = [[0] * (N * 2 + 1)]
count_w = [[0] * (N * 2 + 1)]
for k in range(1, N + 1):
    wc[pos_w[k] + 1] = 1
    bc[pos_b[k] + 1] = 1
    count_b.append(cumsum(bc))
    count_w.append(cumsum(wc))


dp = [[INF] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 0
























for b, w in itertools.product(range(N + 1), repeat=2):
    if b > 0:
        
        orig_pos = pos_b[b]
        inv = b - count_b[b][orig_pos] + w - count_w[w][orig_pos] - 1
        dp[b][w] = min(dp[b][w], dp[b - 1][w] + inv)
    if w > 0:
        
        orig_pos = pos_w[w]
        inv = b - count_b[b][orig_pos] + w - count_w[w][orig_pos] - 1
        dp[b][w] = min(dp[b][w], dp[b][w - 1] + inv)
print(dp[N][N])

Solution (Python):

"""

普通なら転倒数を計算すればよい
でも今回は…？

最終形を確定すればその転倒数を求めればよくなる
何処に白でどこに黒が良いのかを考える…？

2000 C 2 = 2*(10**6) 通り調べるか…？
1回で2000log2000かかるので無理

転倒数をdpする…？
黒の数を保持してdp → 4000 * 4000 log 4000

戻す場合も転倒数は同じ！！→最重要

まずlistに各色・番の初期位置を記録
BWを決めた時にその位置の数字は確定
その並び替えから元に戻す場合の転倒数を計算！！

O(N^2)で解ける！！
dp[i][j] = 左詰めでBをi個,Ｗをj個置いた時の移動回数の最小値
何回動かす必要があるのか？？



"""



def bitadd(a,w,bit): 
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): 
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

"""
def cop(l):

    ret = []
    for i in l:
        ret.append(i)

    return ret


N = int(input())

Blis = [None] * (N+1)
Wlis = [None] * (N+1)

for i in range(N*2):

    c,a = input().split()
    a = int(a)

    if c == "B":
        Blis[a] = i+1
    else:
        Wlis[a] = i+1






BITs = [[0] * (2*N+1)]
revs = [float("inf")] * (N+1)
revs[0] = 0






for i in range(N):

    new = cop(BITs[-1])
    bitadd (Blis[i+1] , 1 , new)
    BITs.append(new)


for i in range(2 * N):

    i += 1

    
    

    for j in range(min(i , N + 1)):

        if i - j <= N:
            bitadd( Wlis[i-j] , 1 , BITs[j] )

    nrevs = [float("inf")] * (N+1)

    for j in range(min(i , N+1)):

        if i - j <= N:
            nrevs[j] = min(nrevs[j] , revs[j] + ( i - bitsum( Wlis[i-j] , BITs[j])))

        if j != N:
            nrevs[j+1] = min(nrevs[j+1] , revs[j] + (i - bitsum( Blis[j+1] , BITs[j+1] )))

    revs = nrevs
print (revs[-1])

"""






N = int(input())

Blis = [None] * (N+1)
Wlis = [None] * (N+1)

for i in range(2*N):

    i += 1

    c,a = input().split()
    a = int(a)

    if c == "B":
        Blis[a] = i
    else:
        Wlis[a] = i



B_bef_B = [0] 
BBIT = [0] * (2 * N + 1)

for i in range(N):
    i += 1

    B_bef_B.append (bitsum(Blis[i] , BBIT))
    bitadd (Blis[i] , 1 , BBIT)

W_bef_W = [0]
WBIT = [0] * (2*N+1)

for i in range(N):
    i += 1
    W_bef_W.append ( bitsum(Wlis[i],WBIT) )
    bitadd (Wlis[i] , 1 , WBIT)








WY_bef_BX = [[0] * (N+1)] 

for x in range(N):
    x += 1

    lis = [0]

    for y in range(N):
        y += 1
        if Wlis[y] < Blis[x]:
            lis.append(lis[-1] + 1)
        else:
            lis.append(lis[-1])

    WY_bef_BX.append(lis)


BY_bef_WX = [[0] * (N+1)]

for x in range(N):
    x += 1

    lis = [0]

    for y in range(N):
        y += 1
        if Blis[y] < Wlis[x]:
            lis.append(lis[-1] + 1)
        else:
            lis.append(lis[-1])

    BY_bef_WX.append(lis)










dp = [ [float("inf")] * (N+1) for i in range(N+1) ]
dp[0][0] = 0

for i in range(2*N): 

    for b in range(i+1):

        w = i-b

        if b < N and w <= N:
            dp[b+1][w] = min(dp[b+1][w] , dp[b][w] + (Blis[b+1] - 1) - (B_bef_B[b+1] + WY_bef_BX[b+1][w]))

        if w < N and b <= N:
            
                
            
            dp[b][w+1] = min(dp[b][w+1] , dp[b][w] + (Wlis[w+1] - 1) - (W_bef_W[w+1] + BY_bef_WX[w+1][b]))


print (dp[-1][-1])

Solution (Python):
from bisect import bisect_right, bisect_left

class BITbisect():
    def __init__(self, InputProbNumbers):
        
        self.ind_to_co = [-10**18]
        self.co_to_ind = {}
        for ind, num in enumerate(sorted(list(set(InputProbNumbers)))):
            self.ind_to_co.append(num)
            self.co_to_ind[num] = ind+1
        self.max = len(self.co_to_ind)
        self.data = [0]*(self.max+1)
    
    def __str__(self):
        retList = []
        for i in range(1, self.max+1):
            x = self.ind_to_co[i]
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    retList.append(x)
        return "[" + ", ".join([str(a) for a in retList]) + "]"
    
    def __getitem__(self, key):
        key += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < key:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max or key < 0:
            raise IndexError("BIT index out of range")
        return self.ind_to_co[ind+1]
    
    def __len__(self):
        return self._query_sum(self.max)
    
    def __contains__(self, num):
        if not num in self.co_to_ind:
            return False
        return self.count(num) > 0
    
    
    
    def _query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    
    
    def _add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i
    
    
    def push(self, x):
        if not x in self.co_to_ind:
            raise KeyError("The pushing number didnt initialized")
        self._add(self.co_to_ind[x], 1)
            
    
    def delete(self, x):
        if not x in self.co_to_ind:
            raise KeyError("The deleting number didnt initialized")
        if self.count(x) <= 0:
            raise ValueError("The deleting number doesnt exist")
        self._add(self.co_to_ind[x], -1)

    
    def count(self, x):
        return self._query_sum(self.co_to_ind[x]) - self._query_sum(self.co_to_ind[x]-1)
    
    
    def bisect_right(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_right(self.ind_to_co, x) - 1
        return self._query_sum(i)

    
    def bisect_left(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_left(self.ind_to_co, x)
        if i == 1:
            return 0
        return self._query_sum(i-1)

import sys
input = sys.stdin.readline
INF = 10**14

N = int(input())
white = [None]*N
blue = [None]*N
for i in range(2*N):
    c, n = map(str, input().rstrip().split())
    if c == "W":
        white[int(n)-1] = i
    else:
        blue[int(n)-1] = i

dp1 = [[0]*(N+1) for _ in range(N+1)]
Indb = BITbisect(list(range(2*N+1)))
for j in reversed(range(N)):
    dp1[N][j] = Indb.bisect_left(blue[j])
    Indb.push(blue[j])
    for i in reversed(range(N)):
        if white[i] < blue[j]:
            dp1[i][j] = dp1[i+1][j] + 1
        else:
            dp1[i][j] = dp1[i+1][j]

dp2 = [[0]*(N+1) for _ in range(N+1)]
Indw = BITbisect(list(range(2*N+1)))
for j in reversed(range(N)):
    dp2[j][N] = Indw.bisect_left(white[j])
    Indw.push(white[j])
    for i in reversed(range(N)):
        if blue[i] < white[j]:
            dp2[j][i] = dp2[j][i+1] + 1
        else:
            dp2[j][i] = dp2[j][i+1]

dp = [[INF]*(N+1) for _ in range(N+1)]
dp[N][N] = 0
for i in reversed(range(N+1)):
    for j in reversed(range(N+1)):
        if i == N:
            if j != N:
                dp[i][j] = dp[i][j+1] + dp1[i][j]
        elif j == N:
            dp[i][j] = dp[i+1][j] + dp2[i][j]
        else:
            dp[i][j] = min(dp[i][j+1]+dp1[i][j], dp[i+1][j]+dp2[i][j])
        
print(dp[0][0])

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

    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


    N = int(input())
    A = [0] * (2*N)
    idx_W = [0] * (N+1)
    idx_B = [0] * (N+1)
    for i in range(N*2):
        c, a = input().split()
        if c == 'B':
            A[i] = int(a)
            idx_B[A[i]] = i+1
        else:
            A[i] = -int(a)
            idx_W[-A[i]] = i + 1

    cost_W = [[0] * (N+2) for _ in range(N+1)]
    cost_B = [[0] * (N+2) for _ in range(N+1)]
    cost_W_imos = [0] * (N+1)
    cost_B_imos = [0] * (N+1)
    for i in range(2*N):
        if A[i] > 0:
            Ai = A[i]
            cost_W_imos[Ai] = 1
            for j in range(N, 0, -1):
                if j == N:
                    cost_B[Ai][j] = cost_B_imos[j]
                else:
                    cost_B[Ai][j] = cost_B[Ai][j+1] + cost_B_imos[j]
        else:
            Ai = -A[i]
            cost_B_imos[Ai] = 1
            for j in range(N, 0, -1):
                if j == N:
                    cost_W[Ai][j] = cost_W_imos[j]
                else:
                    cost_W[Ai][j] = cost_W[Ai][j + 1] + cost_W_imos[j]

    inv_W = [0] * (N+1)
    inv_B = [0] * (N+1)
    bit_W = Bit(2*N+1)
    bit_B = Bit(2*N+1)
    for i in range(N, 0, -1):
        inv_W[i] = bit_W.sum(idx_W[i])
        inv_B[i] = bit_B.sum(idx_B[i])
        bit_W.add(idx_W[i], 1)
        bit_B.add(idx_B[i], 1)

    inf = (N*2)**2
    dp = [[inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N+1):
        for j in range(N+1):
            if i+1 <= N:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + cost_W[i+1][j+1] + inv_W[i+1])
            if j+1 <= N:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + cost_B[j + 1][i + 1] + inv_B[j + 1])
    print(dp[N][N])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate
readline = sys.stdin.readline

class BIT:
    
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.p = 2**(n.bit_length() - 1)
        self.dep = n.bit_length()
    def get(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 bl(self, v):
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s+k]
            k //= 2
        return s + 1

N = int(readline())
W = [0]*N
B = [0]*N
for i in range(1, 2*N+1):
    c, a = readline().split()
    if c == 'W':
        W[int(a)-1] = i
    else:
        B[int(a)-1] = i

cw = [0]*(N+1)
cb = [0]*(N+1)
T = BIT(2*N)
for i in range(N):
    cw[i+1] = i-T.get(W[i])
    T.add(W[i], 1)
T = BIT(2*N)
for i in range(N):
    cb[i+1] = i-T.get(B[i])
    T.add(B[i], 1)

invw = [None] + [[0] + list(accumulate([1 if W[i] < B[j] else 0 for j in range(N)])) for i in range(N)]
invb = [None] + [[0] + list(accumulate([1 if B[i] < W[j] else 0 for j in range(N)])) for i in range(N)]
    
inf = 10**9+7
dp = [[inf]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for s in range(2*N):
    for w in range(max(0, s-N), min(N+1, s+1)):
        b = s-w
        if w != N:
            dp[w+1][b] = min(dp[w+1][b], dp[w][b] + invw[w+1][b] + cw[w+1])
        if b != N:
            dp[w][b+1] = min(dp[w][b+1], dp[w][b] + invb[b+1][w] + cb[b+1])
print(dp[N][N])

Solution (Python):
from itertools import accumulate

n = int(input())
b = []

bc = {}
wc = {}
for i in range(2*n):
    c,a = input().split()
    a = int(a)
    b.append((c,a))
    if c == "B":
        bc[a]=i
    else:
        wc[a]=i


black = [[0]*(n+1) for i in range(n+1)]
white = [[0]*(n+1) for i in range(n+1)]

for i in range(2*n):
    c,a = b[i]
    
    cnt = 0
    num = [0]*(n+1)
    for j in range(i):
        if b[j][0] == c:
            if b[j][1] < a:
                cnt += 1
        else:
            num[b[j][1]] += 1
    
    num = list(accumulate(num))
    if c == "B":
        black[a] = [j+cnt for j in num]
    else:
        white[a] = [j+cnt for j in num]

DP = [[float("inf")]*(n+1) for i in range(n+1)]
DP[0][0] = 0
for i in range(n+1):
    for j in range(n+1):
        
        if i+1 <= n:
            DP[i+1][j] = min(DP[i+1][j], DP[i][j]+bc[i+1]-black[i+1][j])
        if j+1 <= n:
            DP[i][j+1] = min(DP[i][j+1], DP[i][j]+wc[j+1]-white[j+1][i])
print(DP[n][n])

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def main():
    inf = 5000
    n = int(input()[:-1])
    
    cnts = [[[0] * (n + 1) for _ in range(2 * n + 1)] for __ in range(2)]
    pos = [[0] * n for _ in range(2)]
    for i in range(n * 2):
        c, a = input().split()
        c = (c == "W") * 1
        a = int(a) - 1
        pos[c][a] = i
        for cc in range(2):
            for j in range(n):
                if c == cc and a >= j:
                    cnts[cc][i + 1][j] = cnts[cc][i][j] + 1
                else:
                    cnts[cc][i + 1][j] = cnts[cc][i][j]
    
    
    

    dp = [[inf] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for w in range(1, n + 1):
        i = pos[1][w - 1]
        dp[0][w] = dp[0][w - 1] + cnts[0][i][0] + cnts[1][i][w - 1]
    for b in range(1, n + 1):
        i = pos[0][b - 1]
        dp[b][0] = dp[b - 1][0] + cnts[0][i][b - 1] + cnts[1][i][0]
    for b in range(1, n + 1):
        for w in range(1, n + 1):
            bi = pos[0][b - 1]
            wi = pos[1][w - 1]
            dp[b][w] = min(dp[b - 1][w] + cnts[0][bi][b - 1] + cnts[1][bi][w],
                           dp[b][w - 1] + cnts[0][wi][b] + cnts[1][wi][w - 1])
    print(dp[n][n])

main()

Solution (Python):
class BIT():
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

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

	def Add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
s = [input().split() for _ in range(2*n)]
costb = [[0 for _ in range(n+1)] for _ in range(n+1)]
costw = [[0 for _ in range(n+1)] for _ in range(n+1)]
bitb, bitw = BIT(n), BIT(n)
for i in range(2*n-1, -1, -1):
	c, x = s[i][0], int(s[i][1])
	if c == "B":
		base = bitb.Sum(x-1)
		for j in range(n+1):
			costb[x-1][j] = base + bitw.Sum(j)
		bitb.Add(x, 1)
	else:
		base = bitw.Sum(x-1)
		for j in range(n+1):
			costw[j][x-1] = base + bitb.Sum(j)
		bitw.Add(x, 1)

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n+1):
	for j in range(n+1):
		if i+j == 0:
			continue
		if i == 0:
			dp[i][j] = dp[i][j-1] + costw[i][j-1]
		elif j == 0:
			dp[i][j] = dp[i-1][j] + costb[i-1][j]
		else:
			dp[i][j] = min(dp[i][j-1] + costw[i][j-1], dp[i-1][j] + costb[i-1][j])

print(dp[n][n])

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

N = int(input())




B_pos = [0] * (N+1)
W_pos = [0] * (N+1)
B_cnt = [[0] * (N+1) for _ in range(2*N)]
W_cnt = [[0] * (N+1) for _ in range(2*N)]

for i in range(2*N):
    c,a = input().split()
    a = int(a) 
    if c == 'B':
        B_pos[a] = i
    else:
        W_pos[a] = i
for i in range(1,N+1):
    B_cnt[B_pos[i]][i] += 1
    W_cnt[W_pos[i]][i] += 1

for i in range(1,2*N):
    for j in range(N+1):
        B_cnt[i][j] += B_cnt[i-1][j]
        W_cnt[i][j] += W_cnt[i-1][j]
for i in range(2*N):
    for j in range(1,N+1):
        B_cnt[i][j] += B_cnt[i][j-1]
        W_cnt[i][j] += W_cnt[i][j-1]

B_cnt

W_cnt


dp = [[0] * (N+1) for _ in range(N+1)]

INF = 1 << 50
for b in range(N+1):
    rng_w = range(N+1) if b else range(1,N+1)
    for w in rng_w:
        p = B_pos[b]
        q = W_pos[w]
        x1,x2 = INF,INF
        if b >= 1:
            x1 = dp[b-1][w] + (p - B_cnt[p][b-1] - W_cnt[p][w])
        if w >= 1:
            x2 = dp[b][w-1] + (q - W_cnt[q][w-1] - B_cnt[q][b])
        dp[b][w] = x1 if x1 < x2 else x2

answer = dp[N][N]
print(answer)

Solution (Python):
N=int(input())
Ball=[]
for i in range(2*N):
  c,a=input().split()
  Ball.append((c,int(a)))
B=[0]*N
W=[0]*N
B_table=[[0]*(N+1) for i in range(N)]
W_table=[[0]*(N+1) for i in range(N)]
for i in range(2*N):
  c=Ball[i][1]-1
  if Ball[i][0]=="B":
    B[c]=i+1
    for j in range(i+1,2*N):
      if Ball[j][0]=="B":
        if Ball[j][1]<Ball[i][1]:
          B_table[Ball[i][1]-1][0]+=1
      elif Ball[j][0]=="W":
        B_table[c][Ball[j][1]]+=1
    for k in range(N):
      B_table[c][k+1]+=B_table[c][k]
  elif Ball[i][0]=="W":
    W[c]=i+1
    for j in range(i+1,2*N):
      if Ball[j][0]=="W":
        if Ball[j][1]<Ball[i][1]:
          W_table[c][0]+=1
      elif Ball[j][0]=="B":
        W_table[c][Ball[j][1]]+=1
    for k in range(N):
      W_table[c][k+1]+=W_table[c][k]
dp=[[0]*(N+1) for i in range(N+1)]
for s in range(1,2*N+1):
  for b in range(max(0,s-N),min(s,N)+1):
    if b==0:
      dp[0][s]=dp[0][s-1]+(W[s-1]+W_table[s-1][0]-s)
    elif b==s:
      dp[s][0]=dp[s-1][0]+(B[s-1]+B_table[s-1][0]-s)
    else:
      dp[b][s-b]=min(dp[b-1][s-b]+(B[b-1]+B_table[b-1][s-b]-s),dp[b][s-b-1]+(W[s-b-1]+W_table[s-b-1][b]-s))
print(dp[N][N])

Solution (Python):



N = int(input())
balls = []
for _ in range(2 * N):
    c, a = input().split()
    balls += [(c, int(a))]


numB = [[0] * (N + 1) for _ in range(2 * N)]
numW = [[0] * (N + 1) for _ in range(2 * N)]
for i in reversed(range(1, 2 * N)):
    c, a = balls[i]
    numB[i - 1] = list(numB[i])
    numW[i - 1] = list(numW[i])
    if c == 'B':
        for b in range(a, N + 1):
            numB[i - 1][b] += 1
    else:
        for w in range(a, N + 1):
            numW[i - 1][w] += 1


costB = [[0] * (N + 1) for _ in range(N + 1)]
costW = [[0] * (N + 1) for _ in range(N + 1)]
for i in reversed(range(2 * N)):
    c, a = balls[i]
    if c == 'B':
        cost = numB[i][a - 1]
        for w in range(N + 1):
            costB[a - 1][w] = cost + numW[i][w]
    else:
        cost = numW[i][a - 1]
        for b in range(N + 1):
            costW[b][a - 1] = cost + numB[i][b]

INF = 10 ** 9 + 7

dp = [[INF] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 0
for b in range(N + 1):
    for w in range(N + 1):
        if b > 0:
            dp[b][w] = min(dp[b][w], dp[b - 1][w] + costB[b - 1][w])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w - 1] + costW[b][w - 1])

print(dp[N][N])