103761: [Atcoder]ABC376 B - Hands on Ring (Easy)

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.

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

问题陈述

注意：这个问题几乎与问题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$未指定的另一只手。

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

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

约束

• $3 \leq N \leq 100$
• $1 \leq Q \leq 100$
• $H_i$是L或R。
• $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$指令。

1. 移动你的右手作为部分$2 \rightarrow 3 \rightarrow 4$来遵循第一个指令。
2. 移动你的左手作为部分$1 \rightarrow 6 \rightarrow 5$来遵循第二个指令。
3. 移动你的右手作为部分$4 \rightarrow 3