题目描述

有 $2N$ 个球排成一列，其中白球和黑球各 $N$ 个，每个球上写有 $1$ 到 $N$ 的整数，每个数字各出现一次。第 $i$ 个球上写的数字为 $a_i$，颜色为 $c_i$。当 $c_i = \texttt{W}$ 时表示该球为白色，当 $c_i = \texttt{B}$ 时表示该球为黑色。

高桥君有如下目标：

• 对于任意满足 $1 \leq i < j \leq N$ 的整数对 $(i, j)$，写有 $i$ 的白球必须在写有 $j$ 的白球的左侧。
• 对于任意满足 $1 \leq i < j \leq N$ 的整数对 $(i, j)$，写有 $i$ 的黑球必须在写有 $j$ 的黑球的左侧。

为达成目标，高桥君可以进行如下操作：

• 交换相邻的两个球。

请你求出，为达成目标所需的最小操作次数。

输入格式

输入通过标准输入给出，格式如下：

$N$ $c_1$ $a_1$ $c_2$ $a_2$ $\cdots$ $c_{2N}$ $a_{2N}$

输出格式

输出达成目标所需的最小操作次数。

样例 1

输入

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

输出

4

样例 2

输入

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

输出

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

输出

41

说明/提示

限制

• $1 \leq N \leq 2000$
• $1 \leq a_i \leq N$
• $c_i = \texttt{W}$ 或 $c_i = \texttt{B}$
• 若 $i \neq j$，则 $(a_i, c_i) \neq (a_j, c_j)$

样例解释 1

例如如下操作可以在 $4$ 次内完成目标：

• 交换黑色 $3$ 和白色 $1$
• 交换白色 $1$ 和白色 $2$
• 交换黑色 $3$ 和白色 $3$
• 交换黑色 $3$ 和黑色 $2$

由 ChatGPT 4.1 翻译