← 返回题目列表

AtCoder · arc097_c

E. 排序并排序

中文机器翻译题面 查看原题

分数: 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 = W or 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