Problem Description

There are $2 \times n$ carrots in two rows. Each carrot is either a white carrot or a red carrot. We use $a_{i,j} = 0/1$ to represent whether the $i$-th carrot in row $j$ is a white carrot or a red carrot.

Each time, you can pay a cost of $1$ to choose a position that currently has a carrot, and remove all carrots in the 4-connected maximal connected component consisting of carrots of the same color as that carrot. Then, for any carrot in the second row, if the corresponding position in the first row has no carrot, it will fall down to the first row.

Find the minimum total cost to remove all carrots.

Input Format

The first line contains a positive integer $n$, the number of carrots in each row.

The second line contains $n$ integers $0$ or $1$, where the $i$-th one represents $a_{i,2}$.

The third line contains $n$ integers $0$ or $1$, where the $i$-th one represents $a_{i,1}$.

Output Format

Output one integer in one line, which is the answer.

3
0 1 0
1 0 1

4

6
1 0 1 0 0 1
1 1 0 1 0 1

5

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

5

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

11

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

8

Hint

For all test points, $a_{i,j} \in \{0,1\}$, and $1 \leq n \leq 5 \times 10^6$.

This problem uses bundled testdata.

$\sf subtask \ 1: n\leq1 \ \ \ \ \ \ \ \ \ \ \ \ \ 10pts$
$\sf subtask \ 2: n\leq10 \ \ \ \ \ \ \ \ \ \ \ 20pts$
$\sf subtask \ 3: n\leq100 \ \ \ \ \ \ \ \ \ 15pts$
$\sf subtask \ 4: n\leq5000 \ \ \ \ \ \ \ 15pts$
$\sf subtask \ 5: n\leq500000 \ \ \ 20pts$
$\sf subtask \ 6: n\leq5000000 \ 20pts$

Translated by ChatGPT 5