History

题意翻译

B-卡车历史 题目： 先进的货物运输公司使用不同类型的卡车。公司有自己的代码描述每种类型的卡车。代码是一个七位小写字母构成的字符串。在公司建立之初，只有一种卡车类型，但后来衍生出了其他类型，然后从新的类型中又衍生出其他类型，以此类推。 现在历史学家来研究卡车历史。历史学家想要找出所谓的衍生计划——即卡车类型如何被衍生出来。他们将卡车类型的距离定义为卡车类型代码中不同字母的个数。他们还假设, 每种卡车类型都是从另一种卡车类型衍生出来的 (除了第一种卡车类型，它当然不是从任何其他类型衍生出来的)。然后将衍生计划的质量定义为 1/Σ(to, td)d (t0, td) 所求和遍历衍生计划中的所有可成对类型，例如t0是原始的类型, td是从中衍生出的类型，d(t0，td)是这对类型的距离。 因为历史学家失败了，你要写一个程序来帮助他们。给出卡车类型的代码，你的程序应该找到衍生计划中可能的最高质量。 输入： 多组数据。每组数据第一行是卡车类型数N（2<=N<=2000）。接下来N行每行是一种类型的卡车的代码（代码是一个包含七个小写字母的字符串）。你可以假设每个代码描述的类型是唯一的，也就是说在这N行中没有两个相同的字符串。整个输入以一行0结束。 输出： 对于每个测试数据，你的程序应该输出，其中1/Q是最好的衍生计划中的质量。

题目描述

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 $ a_{i} $ to the year $ b_{i} $ inclusive ( $ a_{i}&lt;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}&lt;a_{i} $ and $ b_{i}&lt;b_{j} $ . Your task is simpler: find the number of events that are included in some other event.

输入输出格式

输入格式

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}&lt;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.

输出格式

Print the only integer — the answer to the problem.

输入输出样例

输入样例 #1

5
1 10
2 9
3 8
4 7
5 6

输出样例 #1

4

输入样例 #2

5
1 100
2 50
51 99
52 98
10 60

输出样例 #2

4

输入样例 #3

1
1 1000000000

输出样例 #3

0

说明

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.