题目描述

有 $n\times 2$ 的两列萝卜，萝卜分白萝卜和红萝卜，我们使用 $a_{i,j}=0/1$ 来表示第 $i$ 行第 $j$ 个萝卜是白萝卜还是红萝卜。

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

同时你也可以花初始为 $0$ 的代价，选定 $k=1/2$ 而将第 $k$ 列的所有萝卜上移（$a_{i,k}\to a_{i+1,k}$），并将一个红萝卜即 $1$ 放在第一行第 $k$ 个（$1\to a_{1,k}$），此后这个操作代价 $+1$。

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

输入格式

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

接下来 $n$ 行，第 $i$ 行两个整数分别为 $a_{i,1},a_{i,2}$。

输出格式

一行一个整数表示你的答案

4
0 1
0 1
0 1
0 1

2

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

3

提示

对于所有测试点 $a_{i,j}\in \{0,1\}$，$1\leq n\leq 5\times 10^6$，保证 $a_{i,1}\neq a_{i,2}$。

本题使用捆绑测试
$\sf subtask \ 1: n\leq10 \ \ \ \ \ \ \ \ \ \ \ 30pts $
$\sf subtask \ 2: n\leq100 \ \ \ \ \ \ \ \ \ 20 pts$
$\sf subtask \ 3: n\leq5000 \ \ \ \ \ \ \ 20 pts$
$\sf subtask \ 4: n\leq5000000 \ 30pts$