分数: 250 点
问题陈述
注:该问题与问题F的设置几乎相同,仅正文中粗体部分和约束条件有所不同。
您双手拿着一枚戒指。 该环由 N\ (N \geq 3) 零件编号 1,2,\dots,N,其中零件 i 和 i+1 (1 \leq i \leq N-1) 是相邻的,并且零件 1 和 N 也相邻。
最初,您的左手握住零件 1,并且你的右手拿着部分 2。 合而为一 操作,您可以执行以下操作:
- 将你的一只手移至其当前握持的部分的相邻部分。但是,只有当另一只手不在目标零件上时,您才能执行此操作。
下图显示了初始状态以及可以和不能从该状态进行的操作示例。戒指每个部分上写的数字代表零件编号,标记为 L 和 R 的圆圈分别代表您的左手和右手。

您需要遵循 Q 按顺序向您提供说明。 的 i-th (1 \leq i \leq Q) 指令由字符表示 H_i 和一个整数 T_i,含义如下:
- 执行一定数量的操作(可能为零),以便您的左手(如果 H_i is
L)或你的右手(如果 H_i isR) 正在持有部分 T_i。 在这里,你 不得 移动未指定的另一只手 H_i.
保证只给出可实现的指令。
详细信息
在本题的设定下,可以证明,在跟随之前,双手的位置是唯一确定的 i每个指令 i。 此时,如果我们将左右手的位置表示为零件 l_i 和 r_i分别保证 T_i \neq r_i 当 H_i isL,和 T_i \neq l_i 当 H_i is R.
找出遵循所有指令所需的最少操作总数。
约束
- 3 \leq N \leq 100
- 1 \leq Q \leq 100
- H_i is
LorR. - 1 \leq T_i \leq N
- N, Q,和 T_i 是整数。
- 仅给出可实现的说明(有关详细信息,请参阅问题陈述)。
输入
输入由标准输入按以下格式给出:
N Q H_1 T_1 H_2 T_2 \vdots H_Q T_Q
输出
打印遵循所有说明所需的最少操作总数。
示例输入 1
6 3 R 4 L 5 R 6
示例输出 1
8

通过执行以下操作,您可以遵循所有 Q 按顺序说明。
- 将右手作为一部分移动 2 \rightarrow 3 \rightarrow 4 遵循第一条指令。
- 将左手作为一部分移动 1 \rightarrow 6 \rightarrow 5 遵循第二条指令。
- 将右手作为一部分移动 4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 6 遵循第三条指令。
在这种情况下,操作总数为 2+2+4=8,这是最小值。 (请注意,在执行第三条指令时,您不能将右手作为一部分移动 4 \rightarrow 5 \rightarrow 6.)
示例输入 2
100 2 L 1 R 2
示例输出 2
0
在某些情况下,您可以按照说明进行操作而不执行任何操作。
示例输入 3
30 8 R 23 R 26 R 29 L 20 R 29 R 19 L 7 L 16
示例输出 3
92