Under construction

Still being built. Things may change

Choosing Condos

Interview

Time limit2sMemory limit128 MB

Summary
Count condos that are Pareto-optimal, having no other condo that is both closer to the beach and cheaper.
Level

Medium4 of 10

Topics
Sorting, Greedy
Solved
No attempts yet

Problem

You want to choose condos for a trip. Ideally, a candidate should be inexpensive and close to the beach.

A condo X is a candidate only if it satisfies both conditions below.

  1. Every condo closer to the beach than X has a higher lodging cost than X.
  2. Every condo with a lower lodging cost than X is farther from the beach than X.

Given each condo's distance from the beach and lodging cost, determine how many condos can be candidates.

Input

The first line contains the number of condos N. (1 <= N <= 10000)

Each of the next N lines contains two integers D C, describing one condo. D is its distance from the beach, and C is its lodging cost. (1 <= D, C <= 10000)

No two different condos have both the same D and the same C.

Output

Print the number of condos that can be candidates.

Examples1

  1. Example 1

    Input
    5
300 100
100 300
400 200
200 400
100 500
    Expected output
    2