Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. History

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarpus likes studying at school a lot and he is always diligent about his homework. Polycarpus has never had any problems with natural sciences as his great-great-grandfather was the great physicist Seinstein. On the other hand though, Polycarpus has never had an easy time with history.

Everybody knows that the World history encompasses exactly *n* events: the *i*-th event had continued from the year *a*_{i} to the year *b*_{i} inclusive (*a*_{i} < *b*_{i}). Polycarpus easily learned the dates when each of *n* events started and ended (Polycarpus inherited excellent memory from his great-great-granddad). But the teacher gave him a more complicated task: Polycaprus should know when all events began and ended and he should also find out for each event whether it includes another event. Polycarpus' teacher thinks that an event *j* includes an event *i* if *a*_{j} < *a*_{i} and *b*_{i} < *b*_{j}. Your task is simpler: find the number of events that are included in some other event.

Input

The first input line contains integer *n* (1 ≤ *n* ≤ 10^{5}) which represents the number of events. Next *n* lines contain descriptions of the historical events, one event per line. The *i* + 1 line contains two integers *a*_{i} and *b*_{i} (1 ≤ *a*_{i} < *b*_{i} ≤ 10^{9}) — the beginning and the end of the *i*-th event. No two events start or finish in the same year, that is, *a*_{i} ≠ *a*_{j}, *a*_{i} ≠ *b*_{j}, *b*_{i} ≠ *a*_{j}, *b*_{i} ≠ *b*_{j} for all *i*, *j* (where *i* ≠ *j*). Events are given in arbitrary order.

Output

Print the only integer — the answer to the problem.

Examples

Input

5

1 10

2 9

3 8

4 7

5 6

Output

4

Input

5

1 100

2 50

51 99

52 98

10 60

Output

4

Input

1

1 1000000000

Output

0

Note

In the first example the fifth event is contained in the fourth. Similarly, the fourth event is contained in the third, the third — in the second and the second — in the first.

In the second example all events except the first one are contained in the first.

In the third example only one event, so the answer is 0.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/22/2021 21:37:39 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|