Minimum Domino Removals

The order of the dominoes cannot be changed, and they cannot be rotated. Remove some dominoes so that, for every two adjacent kept dominoes, the right value of the first equals the left value of the next. Find the minimum number of removals.

This site uses a standard input/output protocol.

输入格式

The first line contains N, followed by N lines left right, with values 1..6. This site uses 1≤N≤200000.

输出格式

Output a single integer, the answer.

样例 1

输入：

5
2 4
1 3
4 6
2 4
1 6

输出：

3

样例 2

输入：

3
1 1
1 1
1 1

输出：

0

样例 3

输入：

2
1 2
3 4

输出：

1

样例说明

Example 1: keep the two dominoes (2,4),(4,6) and remove 3. Example 2: all three dominoes chain together, so remove 0. Example 3: none of them chain, so keep any one and remove 1.