AtCoder Regular Contest 097 - Sorted and Sorted

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-----
3
B 1
W 2
B 3
W 1
W 3
B 2

-----Sample Output-----
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.

Source: atcoder | Difficulty: HARD


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


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


from itertools import accumulate

def solve(n, rev):

	def existence_right(rev_c):
		n2 = n * 2
		acc = [[0] * n2]
		row = [0] * n2
		for x in rev_c:
			row[n2 - x - 1] += 1
			acc.append(list(reversed(list(accumulate(row)))))
		return acc
	cost = list(map(existence_right, rev))
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	for (w, x) in enumerate(rev[0]):
		dp[w + 1][0] = dp[w][0] + cost[0][w][x]
	for (b, y) in enumerate(rev[1]):
		dp[0][b + 1] = dp[0][b] + cost[1][b][y]
	for (w, x) in enumerate(rev[0]):
		(dpw0, dpw1) = (dp[w], dp[w + 1])
		(cost_wx, cost_w1) = (cost[0][w][x], cost[0][w + 1])
		for (b, y) in enumerate(rev[1]):
			dpw1[b + 1] = min(dpw0[b + 1] + cost_wx + cost[1][b + 1][x], dpw1[b] + cost_w1[y] + cost[1][b][y])
	return dp[n][n]
n = int(input())
rev = [[0] * n, [0] * n]
for i in range(n * 2):
	(c, a) = input().split()
	a = int(a) - 1
	rev[int(c == 'B')][a] = i
print(solve(n, rev))


N = int(input())
MB = {}
MW = {}
for i in range(2 * N):
	(c, a) = input().split()
	c = 'BW'.index(c)
	a = int(a)
	if c:
		MW[a - 1] = i
	else:
		MB[a - 1] = i
P = [[0] * (N + 1) for i in range(N + 1)]
Q = [[0] * (N + 1) for i in range(N + 1)]
for p in range(N):
	cnt = MW[p] - sum((MW[p0] < MW[p] for p0 in range(p)))
	P[p][0] = cnt
	for q in range(N):
		if MB[q] < MW[p]:
			cnt -= 1
		P[p][q + 1] = cnt
for q in range(N):
	cnt = MB[q] - sum((MB[q0] < MB[q] for q0 in range(q)))
	Q[q][0] = cnt
	for p in range(N):
		if MW[p] < MB[q]:
			cnt -= 1
		Q[q][p + 1] = cnt
dp = [[10 ** 9] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	dp[i + 1][0] = dp[i][0] + P[i][0]
for i in range(N):
	dp[0][i + 1] = dp[0][i] + Q[i][0]
for i in range(N):
	for j in range(N):
		dp[i + 1][j + 1] = min(dp[i][j + 1] + P[i][j + 1], dp[i + 1][j] + Q[j][i + 1])
print(dp[N][N])


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


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


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


from itertools import accumulate

def solve(n, rev):

	def existence_right(rev_c):
		n2 = n * 2
		acc = [[0] * n2]
		row = [0] * n2
		for x in rev_c:
			row[n2 - x - 1] += 1
			acc.append(list(reversed(list(accumulate(row)))))
		return acc
	(cost_w, cost_b) = list(map(existence_right, rev))
	dp = [0] + list(accumulate((c[y] for (y, c) in zip(rev[1], cost_b))))
	for (w, x) in enumerate(rev[0]):
		ndp = [0] * (n + 1)
		cwx = cost_w[w][x]
		ndp[0] = prev = dp[0] + cwx
		for (b, y) in enumerate(rev[1]):
			ndp[b + 1] = prev = min(dp[b + 1] + cwx + cost_b[b + 1][x], prev + cost_w[w + 1][y] + cost_b[b][y])
		dp = ndp
	return dp[n]
n = int(input())
rev = [[0] * n, [0] * n]
for i in range(n * 2):
	(c, a) = input().split()
	a = int(a) - 1
	rev[int(c == 'B')][a] = i
print(solve(n, rev))


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


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


from bisect import bisect
N = int(input())
B = []
BW = []
BB = []
MB = {}
MW = {}
for i in range(2 * N):
	(c, a) = input().split()
	a = int(a)
	c = 'BW'.index(c)
	B.append((c, a))
	if c:
		MW[a - 1] = i
	else:
		MB[a - 1] = i
P = [[0] * (N + 1) for i in range(N + 1)]
Q = [[0] * (N + 1) for i in range(N + 1)]
for p in range(N):
	cnt = MW[p] - sum((MW[p0] < MW[p] for p0 in range(p)))
	P[p][0] = cnt
	for q in range(N):
		if MB[q] < MW[p]:
			cnt -= 1
		P[p][q + 1] = cnt
for q in range(N):
	cnt = MB[q] - sum((MB[q0] < MB[q] for q0 in range(q)))
	Q[q][0] = cnt
	for p in range(N):
		if MW[p] < MB[q]:
			cnt -= 1
		Q[q][p + 1] = cnt
dist = [[10 ** 9] * (N + 1) for i in range(N + 1)]
dist[0][0] = 0
que = [(0, 0, 0)]
for i in range(N):
	dist[i + 1][0] = dist[i][0] + P[i][0]
for i in range(N):
	dist[0][i + 1] = dist[0][i] + Q[i][0]
for i in range(N):
	for j in range(N):
		dist[i + 1][j + 1] = min(dist[i][j + 1] + P[i][j + 1], dist[i + 1][j] + Q[j][i + 1])
print(dist[N][N])


N = int(input())
balls = []
for i in range(2 * N):
	(c, a) = input().split()
	balls += [(c, int(a))]
numB = [[0] * (N + 1) for i in range(2 * N)]
numW = [[0] * (N + 1) for i 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 i in range(N + 1)]
costW = [[0] * (N + 1) for i 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]
dp = [[float('inf')] * (N + 1) for i 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])


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)


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


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


from itertools import accumulate

def solve(n, rev):

	def existence_right(rev_c):
		n2 = n * 2
		acc = [[0] * n2]
		row = [0] * n2
		for x in rev_c:
			row[n2 - x - 1] += 1
			acc.append(list(reversed(list(accumulate(row)))))
		return acc
	cost = list(map(existence_right, rev))
	dp = [0] + list(accumulate((c[y] for (y, c) in zip(rev[1], cost[1]))))
	for (x, cw0, cw1) in zip(rev[0], cost[0], cost[0][1:]):
		ndp = [0] * (n + 1)
		cw0x = cw0[x]
		ndp[0] = prev = dp[0] + cw0x
		for (b, (y, cb0, cb1)) in enumerate(zip(rev[1], cost[1], cost[1][1:])):
			ndp[b + 1] = prev = min(dp[b + 1] + cw0x + cb1[x], prev + cw1[y] + cb0[y])
		dp = ndp
	return dp[n]
n = int(input())
rev = [[0] * n, [0] * n]
for i in range(n * 2):
	(c, a) = input().split()
	a = int(a) - 1
	rev[int(c == 'B')][a] = i
print(solve(n, rev))


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


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


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


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


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)


N = int(input())
L = []
C = []
A = []
b = w = 0
b_d = {}
w_d = {}
for i in range(2 * N):
	(c, a) = input().split()
	a = int(a)
	n = 0
	for (cc, aa) in zip(C, A):
		if cc == c and aa > a:
			n += 1
	L.append([0] * (N + 1))
	cnt = 0
	for j in range(N, -1, -1):
		L[-1][j] = cnt + n
		if j in (b_d if c == 'W' else w_d):
			cnt += 1
	if c == 'B':
		b_d[a] = i
		b += 1
	else:
		w_d[a] = i
		w += 1
	C.append(c)
	A.append(a)
dp = [[0] * (N + 2) for i in range(N + 2)]
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] + L[b_d[j]][i]
		elif j == 0:
			dp[i][j] = dp[i - 1][j] + L[w_d[i]][j]
		else:
			dp[i][j] = min(dp[i - 1][j] + L[w_d[i]][j], dp[i][j - 1] + L[b_d[j]][i])
print(dp[-2][-2])


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


from itertools import accumulate
N = int(input())
balls = []
placeB = [0] * N
placeW = [0] * N
for i in range(2 * N):
	(c, a) = input().split()
	a = int(a)
	balls.append([c, a])
	if c == 'B':
		placeB[a - 1] = i
	else:
		placeW[a - 1] = i
costB = [[0] * (2 * N + 1) for i in range(N + 1)]
costW = [[0] * (2 * N + 1) for i in range(N + 1)]
for i in range(N):
	for j in range(2 * N):
		if balls[j][1] > i:
			if balls[j][0] == 'B':
				costB[i][j + 1] = 1
			else:
				costW[i][j + 1] = 1
costB = [list(accumulate(cB)) for cB in costB]
costW = [list(accumulate(cW)) for cW in costW]
dp = [[float('inf')] * (N + 1) for i 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][placeB[b - 1]] + costW[w][placeB[b - 1]])
		if w > 0:
			dp[b][w] = min(dp[b][w], dp[b][w - 1] + costW[w][placeW[w - 1]] + costB[b][placeW[w - 1]])
print(dp[N][N])


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


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