分数: 600 点
问题陈述
有 2N 球, N 白色和 N 黑色,排成一排。整数来自 1 通过 N 写在白球上,每个球一个,也写在黑球上,每个球一个。
写在上面的整数 i左边第一个球 (1 ≤ i ≤ 2N) 是 a_i,这个球的颜色用字母表示 c_i.
c_i = W 代表球是白球; c_i = B 代表球是黑球。
高桥人类希望实现以下目标:
- 对于每对整数 (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 =
Wor c_i =B. - If i ≠ j, (a_i,c_i) ≠ (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