Steel Slicing 2

Time limit1sMemory limit1024 MB

Summary

Given a histogon of width N made from two mirrored histograms, find the fewest axis-parallel cuts that split it into rectangles.

Level: Hard8 of 10
Topics: Geometry, Greedy, Implementation
Solved: No attempts yet

Problem

ISCO (ICPC Steel Company) buys steel sheets of a certain shape, cuts them into pieces, and sells them in the industry market. Each steel sheet that ISCO buys is shaped like two histograms of equal width, where one histogram is reflected vertically and soldered to the bottom of the other. This forms a polygon without holes, and every side is either horizontal or vertical. We call such a polygon a histogon. See the figure below for a histogon.

A piece sells for much more if it is rectangular, so it is better to cut a steel sheet into several rectangles. A laser cutter does the cutting.

In a single operation, the laser cutter can trace either a horizontal or a vertical segment through a polygon. The segment must touch the polygon's border at exactly two points, the endpoints of the segment. After the cut, the polygon is split into two smaller polygons along the traced path. The laser cutter can only operate on a single polygon in one operation.

The laser cutter is expensive to use. Find the minimum number of laser cutter operations needed so that all resulting polygons are rectangles.

Input

The first line contains $N$ , the width of the histogon ( $1 \le N \le 250\,000$ ).

Each of the next $N$ lines contains two integers $h\_i$ and $l\_i$ . $h\_i$ is the height of the $i$ -th column of the histogram that is not reflected, and $l\_i$ is the height of the $i$ -th column of the reflected histogram. ( $1 \le h\_i, l\_i \le 1\,000\,000$ )

Output

Print a single integer, the minimum number of laser cutter operations needed.

Examples2

Example 1
Input
```
8
1 4
4 2
3 2
5 1
6 4
4 2
2 3
5 1
```
Expected output
```
7
```
Example 2
Input
```
5
23 15
23 17
3 22
15 3
5 1
```
Expected output
```
4
```