## Algorithm

C. History
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Polycarpus 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 ai to the year bi inclusive (ai < bi). 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 aj < ai and bi < bj. 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 ≤ 105) 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 ai and bi (1 ≤ ai < bi ≤ 109) — the beginning and the end of the i-th event. No two events start or finish in the same year, that is, ai ≠ aj, ai ≠ bj, bi ≠ aj, bi ≠ bj for all ij (where i ≠ j). Events are given in arbitrary order.

Output

Print the only integer — the answer to the problem.

Examples
input
Copy
`51 102 93 84 75 6`
output
Copy
`4`
input
Copy
`51 1002 5051 9952 9810 60`
output
Copy
`4`
input
Copy
`11 1000000000`
output
Copy
`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.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

int pairCompare(const std::pair<long,long> &lhs, const std::pair<long,long> &rhs){return (lhs.first < rhs.first);}

int main(){

long n(0); scanf("%ld", &n);

std::vector<std::pair<long, long>> events;
long start(0), finish(0);
for(long k = 0; k < n; k++){
scanf("%ld %ld", &start, &finish);
events.push_back(std::pair<long,long>(start,finish));
}

std::sort(events.begin(), events.end(), pairCompare);

long count(0), currentMaxEnd(0);
for(int k = 0; k < n; k++){
if(events[k].second < currentMaxEnd){++count;}
else{currentMaxEnd = events[k].second;}
}

printf("%ld\n", count);

return 0;
}``````
Copy The Code &

Input

cmd
5
1 10
2 9
3 8
4 7
5 6

Output

cmd
4

## Demonstration

Codeforces Solution-C. History-Solution in C, C++, Java, Python