You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

蒸汽传运，时代来临。

题目描述

滚动的天空（Rolling Sky）是一款快节奏休闲游戏。画面简洁精细，玩家要操作一个滚动的小球在充满障碍和陷阱的平台上往前滚动。游戏操作很简单，玩家只要按住屏幕并划动，就能控制小球是往左滚或者往右滚动，只要成功避开障碍物和陷阱，就能继续前进。游戏内置多个关卡，风格各不相同，障碍众多。

关卡「蒸汽时代」有一个道具，叫作“齿轮镜像推送”。具体来说，当你碰到这个道具，前方的事物（包括障碍物、地板、道具等）会对称翻转。换句话说，你在第 $p$ 行第 $q$ 列碰到了这个道具，那对于 $\forall i\in[1,p)$，在第 $i$ 行第 $j(1\le j\le 5)$ 列的事物，会迅速移到第 $i$ 行第 $6-j$ 列。

结合下图可以更好理解。

（截自 B 站 up 主 @十年叔叔）

其中的 $\colorbox{limegreen}{\color{limegreen}|\kern{-3pt}\color{white}⇄}$ 就是“齿轮镜像推送”。

现在给你 $n\times5$ 的一段路径 $a$，小球从 $a_{n,3}$ 开始向上移动（即所在行号每次减一），当在第 $i(1\le i<n)$ 行，它的位置为 $a_{i,c_i}$。如果球所在位置是障碍物，那么就输了。

如果小球的移动方式不变，要赢（就是走到 $a$ 的第 $1$ 行），应该最少放置几个“齿轮镜像推送”？

注意“齿轮镜像推送”只能放置在地板上。

本题中，我们不讨论钻石、皇冠、跳板，也就是说，我们只关心球的移动。

输入格式

第一行，为一个整数 $n$。

下面 $n$ 行，表示路径 $a$，每行 $5$ 个字母，x 表示障碍物，o 表示地板。

接下来一行有 $n-1$ 个整数，第 $i$ 个整数表示 $c_i$。 （特别的，令 $c_n=3$。）

输出格式

一行一个整数，表示最少放置“齿轮镜像推送”的个数。

如果放置“齿轮镜像推送”也无法赢，输出 N。

3
ooooo
oooxo
ooooo
3 2

0

3
ooxxx
xxxxx
ooooo
1 2

N

5
xoooo
oxxoo
xooox
oxxoo
oxoox
1 2 3 4

1

10
ooooo
xoxxo
ooxoo
oxoox
oxxox
xoooo
ooxox
oxoox
ooxoo
ooooo
4 4 4 4 4 3 2 2 2

3

样例解释

样例 $\textbf1$

初始：

$$\begin{aligned} \tt\color{black}ooooo\\ \tt\color{black}oooxo\\ \tt\color{black}oo\color{red}o\color{black}oo \end{aligned} $$

走到 $a_{2,c_2}=a_{2,2}$：

$$\begin{aligned} \tt\color{black}ooooo\\ \tt\color{black}o\color{red}o\color{black}oxo\\ \tt\color{black}oo\color{red}o\color{black}oo \end{aligned} $$

走到 $a_{1,c_1}=a_{1,3}$：

$$\begin{aligned} \tt\color{black}oo\color{red}o\color{black}oo\\ \tt\color{black}o\color{red}o\color{black}oxo\\ \tt\color{black}oo\color{red}o\color{black}oo \end{aligned} $$

赢了，个数为 $0$。

样例 $\textbf2$

由于第 $2$ 行全是 x，这意味着无论你怎么做都不可能赢。

样例 $\textbf3$

我们在绿色处放置一个“齿轮镜像推送”：

$$\begin{aligned} \tt\color{black}xoooo\\ \tt\color{black}oxxoo\\ \tt\color{black}xooox\\ \tt\color{black}oxx\color{limegreen}o\color{black}o\\ \tt\color{black}ox\color{red}o\color{black}ox\\ \end{aligned} $$

第一次移动，碰到了“齿轮镜像推送”，前方障碍物对称翻转：

$$\begin{aligned} \tt\color{black}oooox\\ \tt\color{black}ooxxo\\ \tt\color{black}xooox\\ \tt\color{black}oxx\color{red}o\color{black}o\\ \tt\color{black}ox\color{red}o\color{black}ox\\ \end{aligned} $$

随后的移动都顺利进行：

$$\begin{aligned} \tt\color{red}o\color{black}ooox\\ \tt\color{black}o\color{red}o\color{black}xxo\\ \tt\color{black}xo\color{red}o\color{black}ox\\ \tt\color{black}oxx\color{red}o\color{black}o\\ \tt\color{black}ox\color{red}o\color{black}ox\\ \end{aligned} $$

所以赢了，个数为 $1$。

数据范围

$2\le n\le 10^5,1\le c_i\le 5$，同时对于 $\forall 2\le i\le n-1$，保证 $|c_i-c_{i-1}|\le1,|c_{n-1}-3|\le 1$。