题目描述
Problem Description
There are $2 \times n$ carrots arranged in two rows, with white and red carrots distinguished by $a_{i,j} = 0/1$, indicating whether the $i$-th carrot in the $j$-th row is white or red.
You can spend 1 unit of cost to select a position with a carrot and remove all carrots in the largest connected block of the same color that includes this carrot. Subsequently, if a carrot in the second row has no corresponding carrot in the first row, it will fall to the first row.
What is the minimum cost to remove all the carrots?
Input Format
The first line contains a positive integer $n$, indicating the number of carrots in each row.
The second line contains $n$ integers, each either 0 or 1, where the $i$-th integer represents $a_{i,2}$.
The third line contains $n$ integers, each either 0 or 1, where the $i$-th integer represents $a_{i,1}$.
Output Format
A single line containing an integer representing your answer.
Sample Input and Output
Input Sample #1
3
0 1 0
1 0 1
Output Sample #1
4
Input Sample #2
6
1 0 1 0 0 1
1 1 0 1 0 1
Output Sample #2
5
Input Sample #3
10
0 0 1 1 1 1 1 1 0 0
0 1 1 0 1 0 0 0 0 1
Output Sample #3
5
Input Sample #4
10
0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0
Output Sample #4
11
Input Sample #5
10
1 0 1 1 1 0 0 1 0 1
0 0 0 1 0 1 0 1 1 0
Output Sample #5
8
Notes
For all test cases, $a_{i,j} \in \{0,1\}$ and $1 \leq n \leq 5 \times 10^6$.
This problem uses bundled test cases
$\sf subtask \ 1: n\leq1 \ \ \ \ \ \ \ \ \ \ \ \ \ 10pts$
$\sf subtask \ 2: n\leq10 \ \ \ \ \ \ \ \ \ \ \ 20pts$
$\sf subtask \ 3: n\leq100 \ \ \ \ \ \ \ \ \ 15$
$\sf subtask \ 4: n\leq5000 \ \ \ \ \ \ \ 15$
$\sf subtask \ 5: n\leq500000 \ \ \ 20pts$
$\sf subtask \ 6: n\leq5000000 \ 20pts$
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分