AT_joi2021_yo2_a 往復すごろく (Round Sugoroku)

JOI 高中的葵购买了一款新的双六棋盘。这款双六棋盘由 $N+2$ 个格子横向排列而成。这些格子从左到右依次编号为 $0$ 到 $N+1$。初始时，格子 $0$ 和格子 $N+1$ 上写有 `X`，格子 $i$（$1 \leq i \leq N$）上写有 $S_i$。其中，$S_i$ 是字符 `.` 或 `#`。 葵用这款双六棋盘和一个棋子进行游戏。最开始，棋子被放置在格子 $A$（$1 \leq A \leq N$）上，面朝右方。此时，$S_A$ 一定是 `.`。每经过 $1$ 秒，棋子会按当前朝向移动到相邻的一个格子。 该双六棋盘有如下**规则**： - 当棋子停在写有 `X` 的格子上时，棋子的朝向会反转。 - 当棋子停在写有 `.` 的格子上时，什么都不会发生。 - 当棋子停在写有 `#` 的格子上时，棋子的朝向会反转，并且该格子上的字符会被改为 `.`。因此，之后棋子再停在这个格子上时，朝向不会再反转。 此外，棋子的反转和字符的更改所需时间可以忽略不计。 给定双六棋盘和棋子的初始状态，请编写程序计算所有写有 `#` 的格子都被消除所需的时间。

输入从标准输入按以下格式给出： > $N$ $A$ $S$ 其中，$S$ 是一个长度为 $N$ 的字符串，第 $i$ 个字符（$1 \leq i \leq N$）为 $S_i$。

请输出使所有写有 `#` 的格子都被消除所需的秒数。

### 限制条件 - $2 \leq N \leq 200\,000$。 - $1 \leq A \leq N$。 - $S_i$ 是字符 `.` 或 `#`（$1 \leq i \leq N$）。 - $S_A$ 是字符 `.`。 - 至少存在一个 $i$（$1 \leq i \leq N$），使得 $S_i$ 是 `#`。 ### 子任务 1.（40 分）$N \leq 3\,000$。 2.（60 分）无额外限制。 ### 样例解释 1 随着时间的推移，双六棋盘的状态如下所示。右向棋子用 `>` 表示，左向棋子用 `#..#X` 2. `X.#....#X` 6. `X...>..#X` 7. `X....>.#X` 8. `X.....>#X` 9. `X......` ### 样例解释 2 随着时间的推移，双六棋盘的状态如下所示。 1. `X>#.#X` 2. `X...#X` 6. `X.>.#X` 7. `X..>#X` 8. `X...` 由 ChatGPT 4.1 翻译