题目描述

有一个 $2 \times n$ 的格子，每个格子里有一个萝卜。萝卜分为白萝卜和红萝卜，分别用 $0$ 和 $1$ 表示。第 $i$ 列第一行的萝卜种类记为 $a_{i,1}$，第二行的萝卜种类记为 $a_{i,2}$。

你每次可以花费 $1$ 的代价，选择一个有萝卜的格子，然后将这个格子所在的同种颜色萝卜构成的四连通极大连通块中的所有萝卜全部拿走。随后，如果第二行某个格子的萝卜被拿走，而它正上方的第一行格子没有萝卜，则该萝卜会掉落到第一行对应的格子上。

你的目标是拿走所有萝卜，求最小的总代价。

输入格式

第一行一个正整数 $n$，表示每行萝卜的数量。

第二行 $n$ 个整数，每个为 $0$ 或 $1$，表示第一行每个位置的萝卜种类。

第三行 $n$ 个整数，每个为 $0$ 或 $1$，表示第二行每个位置的萝卜种类。

输出格式

输出一行一个整数，表示拿走所有萝卜的最小代价。

样例

3
0 1 0
1 0 1

4

10
0 0 1 1 1 1 1 1 0 0
0 1 1 0 1 0 0 0 0 1

5

数据范围与提示

• 对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^6$。
• 每个萝卜种类为 $0$ 或 $1$。

来源

CSPJ-重点算法班