AT_abc376_f [ABC376F] Hands on Ring (Hard)

**注：本题与 B 题几乎相同，仅有正文中加粗部分及约束条件不同。** 你正用双手握住一个环。这个环由 $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$ 表示，其含义如下： - 通过若干次操作（可以为 $0$ 次），使得如果 $H_i$ 为 `L`，则左手，若为 `R`，则右手，握住部件 $T_i$。此时，**可以移动未被 $H_i$ 指定的另一只手**。 **在本题的设定和约束下，可以证明任意指示都可以达成。** 请你求出，为了依次完成所有指示，所需操作次数的最小总和。

输入按以下格式从标准输入读入。 > $N$ $Q$ > $H_1$ $T_1$ > $H_2$ $T_2$ > $\vdots$ > $H_Q$ $T_Q$

请输出依次完成所有指示所需操作次数的最小总和。

## 约束 - $3\leq N \leq 3000$ - $1\leq Q \leq 3000$ - $H_i$ 为 `L` 或 `R` - $1\leq T_i\leq N$ - $N,Q,T_i$ 均为整数 ## 样例解释 1  可以按如下方式操作，依次完成 $Q$ 条指示： 1. 右手依次移动到部件 $2\rightarrow 3\rightarrow 4$，完成第 1 条指示。 2. 左手依次移动到部件 $1\rightarrow 6\rightarrow 5$，完成第 2 条指示。 3. 左手移动到部件 $5\rightarrow 6$，然后右手移动到部件 $4\rightarrow 5$，完成第 3 条指示。 此时操作总次数为 $2+2+1+1=6$，且这是最小值。 ## 样例解释 2 有时无需进行任何操作即可完成指示。 由 ChatGPT 4.1 翻译