Problem Description

A 2D Cartesian coordinate system is given.

We require that a polyline can be drawn in one stroke only from left to right, and the angle between each segment of the polyline and the $x$-axis is in $[-45^\circ, 45^\circ]$.

A polyline that satisfies the above requirements is called a straight polyline.

Given $n$ lattice points on the coordinate plane, what is the minimum number of straight polylines needed to cover all the points?

Input Format

The first line contains a positive integer $n$, representing the number of points.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th point.

Output Format

Output a single integer, representing the minimum number of straight polylines required.

5
2 3
3 4
4 5
1 6
12 27

3

6
1 6
10 8
1 5
2 20
4 4
6 2

3

Hint

For $100\%$ of the testdata, $1 \le n \le 30000$, $0 \le x_i, y_i \le 30000$.

Translated by ChatGPT 5