Circle Regions

Time limit1sMemory limit256 MB

Summary

Count how many regions N circles with centers on the x-axis and no crossings cut the plane into.

Level: Medium7 of 10
Topics: Stack, Sorting, Union-find, Math
Solved: No attempts yet

Problem

There are $N$ circles on the x-axis. Every center lies on the x-axis, and no two circles cross each other. They may touch.

Write a program that counts how many regions the circles cut the plane into.

A region is a set of points, and any two points in it can be joined by a continuous curve that never meets a circle. The unbounded part outside every circle counts as one region.

Input

The first line contains the number of circles $N$ ( $1 \le N \le 300\,000$ ).

Each of the next $N$ lines contains one circle as two integers $x_i$ and $r_i$ . $x_i$ is the x coordinate of the center and $r_i$ is the radius. ( $-10^9 \le x_i \le 10^9$ , $1 \le r_i \le 10^9$ )

No circle is given twice.

Output

Print the number of regions the circles make.

Examples3

Example 1
Input
```
2
1 3
5 1
```
Expected output
```
3
```
Example 2
Input
```
3
2 2
1 1
3 1
```
Expected output
```
5
```
Example 3
Input
```
4
7 5
-9 11
11 9
0 20
```
Expected output
```
6
```