Description

有2×n 的两行萝卜，萝卜分白萝卜和红萝卜，我们使用aij=0/1 来表示第 j 行第 i 个萝卜是白萝卜还是红萝卜。

你每次可以花 1 的代价，选定一个有萝卜的位置，并将这个萝卜所在的由同种颜色萝卜所构成的连通极大连通块的萝卜全部拿走，然后一个在第二行的萝卜如果其对应的第一行的位置没有萝卜，就会掉落至第一行。

请问拿走所有萝卜的最小代价是多少。

Input Format

第一行包含一个正整数 n 表示每行有多少个萝卜。

第二行有 n 个 0 或 1 的整数,其中第 i 个表示 ai,2。

第三行有 n 个 0 或 1 的整数,其中第 i 个表示 ai,1。

对于所有测试点aij∈{0,1}，1≤n≤5e6。

样例2：

输入

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

输出

5

Output Format

3
0 1 0
1 0 1

4

Source