Counting Stars

Program time limit: 1 second

Program memory limit: 512 MB

Before you is a vast star-scape with a myriad of stars and shooting stars sailing before your eyes.

You raise your camera to your eye and take a burst of photos of the sky over a second or so. Each photo within the set of burst photos perfectly captures the location of every star in frame at the moment of capture.

During this period of time, you reliably recall that from where you're standing, shooting stars only ever move from your left to your right, and only from high to low (stars will not ever move perfectly horizontally or perfectly vertically). Though the shooting stars didn't always have to move in smooth trajectories because they're a bit special :>

Assuming (correctly) that you've kept your camera perfectly still as you took the burst, you overlay all photos you took during that burst and turn it into one image. So for each star that exists in any of the images taken in the burst, it will appear on this final image. If a shooting star appears in multiple images in the set of burst photos, but in different locations (because it moved), it will appear in all of these locations. Just from looking at this final image, at least how many stars must have existed in the patch of sky you captured with your camera?

Notes:

You cannot assume that the intervals within the burst of photos you've taken is evenly spaced out. Nor can you assume shooting stars will move at a constant/sensible velocity, only that they move up to down, left to right.
It is possible that none, any, or all of the stars you captured are shooting stars.

Input

The first line contains an integer $n$, the total number of stars seen in the final photo obtained by by overlaying all photos in the burst.

This is followed by $n$ lines, each consisting of a pair of space seperated integers $x$ $y$
where each pair $(x, y)$ represents the coordinate of a star that appears in this final image.

Constraints

Subtask 1 (60%):

$1 \le N \le 1000$
$1 \le x, y \le 10^{9}$

Subtask 2 (40%):

$1 \le N \le 200 000$
$1 \le x, y \le 10^{9}$

Output

A single integer: the minimum number of stars in the patch of sky (given the final image).

Sample Input 1

Sample Output 1

Explaination 1

$(0, 2)$ and $(2, 1)$ can be from one shooting star $(1, 4)$, $(2, 3)$ and $(7, 2)$ can be from another shooting star $(0, 0)$ must be from a separate star

Sample Input 2

Sample Output 2

Scoring

Your program will be run on the 2 sample cases and multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves the subtask. Recall that your final score on the task is the score of your highest scoring submission.

Submit

Past submissions

You haven't submitted to this task.