配点 : $600$ 点

問題文

それぞれ $1$ から $N$ の整数が $1$ つずつ書かれた白いボールと黒いボールが合わせて $2N$ 個一列に並んでいます。 左から $i$ ($1$ $\leq$ $i$ $\leq$ $2N$) 個目のボールに書いてある数は $a_i$ で、色は $c_i$ で表されます。 $c_i$ $=$ W のとき ボールが白いことを、$c_i$ $=$ B のとき ボールが黒いことを表します。

人間の高橋君は次のような目標を達成したいです。

• $1$ $\leq$ $i$ $<$ $j$ $\leq$ $N$ を満たす任意の整数の組 $(i,j)$ に対して、$i$ が書かれた白いボールの方が $j$ が書かれた白いボールより左にある
• $1$ $\leq$ $i$ $<$ $j$ $\leq$ $N$ を満たす任意の整数の組 $(i,j)$ に対して、$i$ が書かれた黒いボールの方が $j$ が書かれた黒いボールより左にある

目標を達成するために高橋君は次のような操作ができます。

• 隣り合う二つのボールをスワップする

目標を達成するために必要な操作回数の最小値を求めてください。

制約

• $1$ $\leq$ $N$ $\leq$ $2000$
• $1$ $\leq$ $a_i$ $\leq$ $N$
• $c_i$ $=$ W または $c_i$ $=$ B
• $i$ $\neq$ $j$ なら、 $(a_i,c_i)$ $\neq$ $(a_j,c_j)$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$c_1$ $a_1$

$c_2$ $a_2$

$:$

$c_{2N}$ $a_{2N}$

出力

目標を達成するために必要な操作回数の最小値を出力せよ。

3
B 1
W 2
B 3
W 1
W 3
B 2

4

例えば次のようにすると $4$ 回で可能です。

• 黒の $3$ と白の $1$ をスワップ
• 白の $1$ と白の $2$ をスワップ
• 黒の $3$ と白の $3$ をスワップ
• 黒の $3$ と黒の $2$ をスワップ

4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1

18

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

41