133. Border¶
time limit per test: 0.25 sec / memory limit per test: 4096 KB
Along the border between states A and B there are N defence outposts. For every outpost k, the interval [ \(A_k,B_k\)] which is guarded by it is known. Because of financial reasons, the president of country A decided that some of the outposts should be abandoned. In fact, all the redundant outposts will be abandoned. An outpost i is redundant if there exists some outpost j such that \(A_j<A_i\) and \(B_i<B_j\). Your task is to find the number of redundant outposts.
Input
The first line of the input will contain the integer number N (1<=N<=16 000). N lines will follow, each of them containing 2 integers: \(A_k\) and \(B_k\) (0 <= \(A_k\) < \(B_k\) <= 2 000 000 000), separated by blanks. All the numbers \(A_k\) will be different. All the numbers \(B_k\) will be different.
Output
You should print the number of redundant outposts.
| Sample Input | Sample Output |
5
0 10
2 9
3 8
1 15
6 11
|
3
|