Score : $250$ points

问题陈述

注意：这个问题的设置几乎与问题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$个（$1 \leq i \leq Q$）指令由一个字符$H_i$和一个整数$T_i$表示，含义如下：

• 执行一些操作（可能是零），使你的左手（如果$H_i$是L）或右手（如果$H_i$是R）拿着第$T_i$部分。这里，你不能移动$H_i$未指定的另一只手。

保证只给出可实现的指令。

在这个问题的设置下，可以证明，在遵循第$i$个指令之前，两只手的位置是唯一确定的。在那时，如果我们将左手和右手的位置分别表示为部分$l_i$和$r_i$，那么当$H_i$是L时，保证$T_i \neq r_i$，当$H_i$是R时，保证$T_i \neq l_i$。

找出遵循所有指令所需的最小总操作数。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

Note: This problem has almost the same setting as Problem F. Only the parts in bold in the main text and constraints differ.

You are holding a ring with both hands. This ring consists of $N\ (N \geq 3)$ parts numbered $1,2,\dots,N$, where parts $i$ and $i+1$ ($1 \leq i \leq N-1$) are adjacent, and parts $1$ and $N$ are also adjacent.

Initially, your left hand is holding part $1$, and your right hand is holding part $2$. In one operation, you can do the following:

• Move one of your hands to an adjacent part of the part it is currently holding. However, you can do this only if the other hand is not on the destination part.

The following figure shows the initial state and examples of operations that can and cannot be made from there. The number written on each part of the ring represents the part number, and the circles labeled L and R represent your left and right hands, respectively.

You need to follow $Q$ instructions given to you in order. The $i$-th ($1 \leq i \leq Q$) instruction is represented by a character $H_i$ and an integer $T_i$, meaning the following:

• Perform some number of operations (possibly zero) so that your left hand (if $H_i$ is L) or your right hand (if $H_i$ is R) is holding part $T_i$. Here, you must not move the other hand not specified by $H_i$.

It is guaranteed that only achievable instructions are given.

Details Under the settings of this problem, it can be proved that the positions of both hands are uniquely determined just before following the $i$-th instruction for each $i$. At that time, if we denote the positions of the left and right hands as parts $l_i$ and $r_i$, respectively, it is guaranteed that $T_i \neq r_i$ when $H_i$ is L, and $T_i \neq l_i$ when $H_i$ is R.

Find the minimum total number of operations required to follow all the instructions.

Constraints

• $3 \leq N \leq 100$
• $1 \leq Q \leq 100$
• $H_i$ is L or R.
• $1 \leq T_i \leq N$
• $N$, $Q$, and $T_i$ are integers.
• Only achievable instructions are given (see the problem statement for details).

Input

The Input is given from Standard Input in the following format:

$N$ $Q$

$H_1$ $T_1$

$H_2$ $T_2$

$\vdots$

$H_Q$ $T_Q$

Output

Print the minimum total number of operations required to follow all the instructions.

Sample Input 1

6 3
R 4
L 5
R 6

Sample Output 1

8

By performing the following operations, you can follow all $Q$ instructions in order.

1. Move your right hand as part $2 \rightarrow 3 \rightarrow 4$ to follow the first instruction.
2. Move your left hand as part $1 \rightarrow 6 \rightarrow 5$ to follow the second instruction.
3. Move your right hand as part $4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 6$ to follow the third instruction.

In this case, the total number of operations is $2+2+4=8$, which is the minimum. (Note that when following the third instruction, you cannot move your right hand as part $4 \rightarrow 5 \rightarrow 6$.)

Sample Input 2

100 2
L 1
R 2

Sample Output 2

0

There are cases where you can follow the instructions without performing any operations.

Sample Input 3

30 8
R 23
R 26
R 29
L 20
R 29
R 19
L 7
L 16

Sample Output 3

92