cho.sh
Notes
Loading...

Easy Skyline

Time limit

2s

Memory limit

128 MB

Problem

The outline made by buildings at sunset is called a skyline. From the skyline alone, it is usually impossible to know exactly how many buildings exist. However, if every building is an axis-aligned rectangle, it is possible to determine the minimum number of buildings needed to produce the given skyline.

Given the points where the skyline height changes, compute this minimum number of buildings.

Input

The first line contains n, the number of height-change points in the skyline. (1 ≤ n ≤ 50,000)

Each of the next n lines contains x and y, the coordinate of a point where the skyline height changes as you scan from left to right, and the height from that point onward. (1 ≤ x ≤ 1,000,000, 0 ≤ y ≤ 500,000)

The x-coordinate of the first point is always 1.

Output

Print the minimum number of buildings needed.

Hint

The input describes the skyline below.

...............................XX.........XXX........XXX.XX.......XXXXXXX.....XXXXXXXXXX....XXXXXXXXXXXX

It can be formed with six buildings as shown below, and no smaller number of buildings is possible.

...............................22.........333........111.22.......XX333XX.....X111X22XXX....XX333XXXXXXX
...............................XX.........XXX........XXX.XX.......5555555.....4444444444....5555555XXXXX
...............................XX.........XXX........XXX.XX.......XXXXXXX.....XXXXXXXXXX....666666666666
...............................XX.........XXX........XXX.XX.......XXXXXXX.....XXXXXXXXXX....XXXXXXXXXXXX
...............................22.........333........111.22.......XX333XX.....X111X22XXX....XX333XXXXXXX
...............................XX.........XXX........XXX.XX.......5555555.....4444444444....5555555XXXXX
...............................XX.........XXX........XXX.XX.......XXXXXXX.....XXXXXXXXXX....666666666666