AT_abc376_f [ABC376F] Hands on Ring (Hard)

[problemUrl]: https://atcoder.jp/contests/abc376/tasks/abc376_f **注：この問題は B 問題とほぼ同じ設定です。本文中で太字で示されている部分および制約のみが異なります。** あなたはあるリングを両手で握っています。 このリングは $ N\ (N\geq\ 3) $ 個のパーツ $ 1,2,\dots,N $ によって構成されており、パーツ $ i $ とパーツ $ i+1 $ ($ 1\leq\ i\leq\ N-1 $)、およびパーツ $ 1 $ とパーツ $ N $ がそれぞれ隣接しています。 最初、左手はパーツ $ 1 $ を、右手はパーツ $ 2 $ を握っています。 あなたは、$ 1 $ 回の *操作* で以下のことを行えます。 - 片方の手を、今握っているパーツに隣接するいずれかのパーツに移動する。ただし、移動先にもう一方の手がない場合に限る。 以下の図は、初期状態およびそこから行える操作と行えない操作の例を示したもので、リングの各パーツに書き込まれた数はそのパーツの番号を、L と書かれた丸は左手を、R と書かれた丸は右手を示しています。  あなたは今から与えられる $ Q $ 個の指示に順番に従う必要があります。 $ i\ (1\leq\ i\leq\ Q) $ 個目の指示は文字 $ H_i $ および整数 $ T_i $ によって表され、その意味は以下の通りです： - 操作を何回か（$ 0 $ 回でもよい）行うことで、$ H_i $ が `L` ならば左手、`R` ならば右手が、パーツ $ T_i $ を握っている状態にする。 このとき、$ H_i $ によって指定された手ではない方の手を **動かしてもよい**。 **なお、本問題の設定および制約の下では、どのような指示も達成可能なことが証明できます。** すべての指示に従うために必要な操作回数の合計の最小値を求めてください。

N/A

N/A

### 制約 - $ 3\leq\ N\ \leq\ 3000 $ - $ 1\leq\ Q\ \leq\ 3000 $ - $ H_i $ は `L` または `R` - $ 1\leq\ T_i\leq\ N $ - $ N,Q,T_i $ は整数 ### Sample Explanation 1 !\[\](https://img.atcoder.jp/abc376/d9baddfa26f7a1ccd163cbd8ad01fde4.png) 以下のように操作を行うことで、$ 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 $ であり、これが最小です。 ### Sample Explanation 2 操作を $ 1 $ 度も行わずに指示に従うことができる場合もあります。