U433552 舞蹈家怀特先生

纯粹纪念碑题目 **(完改版)** ($2024.5.21$ 新增 $Markdown\ and\ KaTex$ 及一些文字的问题。新添一些剧情文字，方便做题者阅读并 $AC$ 此题。) $Mr.HuaiTe$

怀特先生是一个**大胖子**。他很喜欢玩跳舞机 $（Dance Dance Revolution, DDR）$，甚至他希望有朝一日人家会叫他“**舞蹈家怀特先生**”。可以说是志向十分远大。 可惜现在他的动作根本不能称作是在跳舞，而倒是像在马戏团表演，尽管每次他都十分投入的跳。这也难怪，有他这样的体型，玩跳舞机是相当费劲的。所以他决定购买一台 $DDR$，由你负责监督他的跳舞工作。 而他希望你写一个程序来**安排舞步**，能让他跳起来轻松一些，至少不要每次都汗流浃背。 $DDR$ 的主要内容是用脚来踩踏板。 踏板有四个方向的箭头，分别使用 $1 (Up)、2 (Left)、3 (Down)、4 (Right)$ 来代表，中间位置由 $0$ 来代替。每首歌曲都有一个箭头序列，游戏者**必须**按照或这个序列一次用某一只脚踩相应的踏板。 在任何时候，两只脚**都不能在同一踏板上**，但可以同时待在中心位置 $0$。 每一个时刻，它必须移动而且只能移动他的一只脚去踩相应的箭头，而另一只脚不许移动。 这样，它跳 $DDR$ 的方式可以用一串数字 $l1, l2,\dots , ln$ 来表示，其中 $li=0$ 表示他用左脚踩第 $i$ 个箭头，$li=1$ 表示他用右脚踩第 $i$ 个箭头。 跳完一首曲子之后，怀特先生会**计算**他所消耗的体力。从中心移动到任何一个箭头耗费 $2$ 单位体力，从任何一个箭头移动到相邻箭头耗费 $3$ 单位体力，移动到相对的箭头（$1$ 和 $3$ 相对，$2$ 和 $4$ 相对）耗费 $4$ 单位体力，而留在原地再踩一下只需要 $1$ 单位。 现在，有一个长度为 $n$ 的箭头序列 $S_1$， 怀特先生应该怎样移动他的双脚（即，对于每个箭头，选一只脚去踩它），才能用最少的体力完成一首给定的舞曲呢？ 例如，对于箭头序列 $Left (2), Left (2), Up (1), Right (4)$，他应该分别用 **左、左、右、右**脚去踩，总的体力耗费为 $2+1+2+3=8$ 单位.

第一行一个数 $n$，表示序列的长度。 第二行一个数字序列 $S_1$ 表示安排的舞步。

一个整数 $W$，表示怀特先生跳完这一段舞所需要花费的最少的体力值。

**数据规模** $n \le 5 \times 10^{5}$，$|S_1|=n$ ### 样例1解释 当舞曲长度为 $4$ 且箭头序列为 $2244$ 时： > 第一个箭头指向左侧，任意的脚均可踩到此点，代价为 $2$。 > > 第二个箭头也指向左侧，上一个迈出的脚踩到此点即可，代价为 $1$。 > > 第三个箭头指向右侧，迈出与上一个迈出的脚相反的脚即可，代价为 $2$。 > > 最后一个箭头也指向右侧，迈出与上一个迈出的脚相同的脚即可，代价为 $1$。 **所以**，综上，最小代价为 $2+1+2+1=6$。