Description

Bocchi the Builder 刚刚完成了她的最新项目：一条由两排白色等边三角形瓷砖组成的小巷。然而，在最后一刻，灾难降临了！她不小心把黑色油漆洒在了一些瓷砖上。现在，一些瓷砖是湿的，其他瓷砖是干的。Bocchi 必须在所有湿的区域周围放置警示胶带。你能帮她确定她需要多少米的胶带吗？

第一个三角形瓷砖将指向上方。每对相邻的瓷砖（即共享一条边的瓷砖）将指向相反的方向。每块瓷砖的边长为 1 米。

Input Format

输入的第一行将包含一个正整数 $C$，表示列数。

接下来的两行每行将包含 $C$ 个用空格分隔的整数。每个整数表示沿小巷的一个瓷砖的颜色，1 表示瓷砖是黑色（湿的），0 表示瓷砖是白色（干的）。

下表显示了可用的 15 分数是如何分配的：

Output Format

输出一个整数，表示 Bocchi 需要的胶带长度，以米为单位。

5
1 0 1 0 1
0 0 0 0 0

9

7
0 0 1 1 0 1 0
0 0 1 0 1 0 0

11

Hint

本题采用捆绑测试。

• 子任务 $1$（$3$ 分）：$C \leq 2 \times 10^3$，黑色三角形不相邻，第二行全部为白色三角形。
• 子任务 $2$（$3$ 分）：$C \leq 2 \times 10^3$，黑色三角形可能相邻，第二行全部为白色三角形。
• 子任务 $3$（$5$ 分）：$C \leq 2 \times 10^3$，黑色三角形可能相邻，第二行可能有黑色三角形。
• 子任务 $4$（$4$ 分）：$C \leq 2 \times 10^5$，黑色三角形可能相邻，第二行可能有黑色三角形。

样例 $1$ 图解：

样例 $2$ 图解：

题面翻译由 ChatGPT-4o 提供。