题目描述

有 $2N$ 个球，$N$ 个白色球和 $N$ 个黑色球，排列在一行上。将 $1$ 到 $N$ 的整数分别写在白球和黑球上，每个球上都写有一个整数。从左边开始第 $i$ 个球（$1$ $≤$ $i$ $≤$ $2N$）上的整数是 $a_i$，该球的颜色由字母 $c_i$ 表示。$c_i$ \= W 表示球是白色；$c_i$ \= B 表示球是黑色。

Takahashi 想要实现以下目标：

• 对于所有的整数对 $(i,j)$，满足 $1$ $≤$ $i$ $<$ $j$ $≤$ $N$，写着整数 $i$ 的白球在写着整数 $j$ 的白球的左边。
• 对于所有的整数对 $(i,j)$，满足 $1$ $≤$ $i$ $<$ $j$ $≤$ $N$，写着整数 $i$ 的黑球在写着整数 $j$ 的黑球的左边。

为了实现这个目标，他可以执行以下操作：

• 交换相邻的两个球。

找出实现这个目标所需的最小操作次数。

约束条件

• $1$ $≤$ $N$ $≤$ $2000$
• $1$ $≤$ $a_i$ $≤$ $N$
• $c_i$ \= W 或 $c_i$ \= B。
• 如果 $i$ $≠$ $j$，$(a_i,c_i)$ $\ne$ $(a_j,c_j)$。

输入

输入以以下格式从标准输入获得：

$N$ $c_1$ $a_1$ $c_2$ $a_2$ $:$ $c_{2N}$ $a_{2N}$

输出

打印实现这个目标所需的最小操作次数。

示例输入 1

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

示例输出 1

4

可以通过四次操作实现目标，例如：

• 交换黑球 $3$ 和白球 $1$。
• 交换白球 $1$ 和白球 $2$。
• 交换黑球 $3$ 和白球 $3$。
• 交换黑球 $3$ 和黑球 $2$。

示例输入 2

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

示例输出 2

18

示例输入 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

示例输出 3

41