Line Overlap Problem

Calculating the overlapping of line segments is the fundamental problem of computational geometry. In this problem, we consider the simplified line overlap problem – how to calculate the overlapping length of horizontal line segments.

In this problem, all horizontal lines have no y-coordinate, and they can be regarded to have the same y-coordinate. Thus the overlapping check can be achieved by only examining the x-coordinates of two endpoints of every line segment. You have to identify all two line pairs with overlap and sum up the total overlapping length. For example, there are three line segments and any two line segments overlap. Thus you have to find three overlapping lengths and then sum up these three overlapping lengths. Two-loop codes can simply solve this problem, but its time complexity is O(n2), where n is the number of line segments. The runtime will increase substantially as n increases. The time complexity of the optimal solution to this problem is O(nlogn). All benchmarks in this contest can be solved within 0.156 second on the contest platform. Please design an algorithm to calculate the overlapping length of a horizontal line set and guarantee to solve each benchmark within 2 seconds (including 2 seconds). Any test for a benchmark over 2 seconds is regarded to fail.

Input

The input consists of N (N < 200000) datasets representing horizontal lines, followed by a line which contains only a single ‘.’ (period). There are two integers i and j in a line, where the first integer i (i < 100000) is the x-coordinate of left endpoint and the second integer j (j < 100000) is the x-coordinate of right endpoint. Two integers are separated by space character. Notably, the number of space characters is not fixed, do not use space-sensitive instruction to read input file.

For example, the following input dataset is described as follows.

75 325

5 120

100 255

325 500

There are four horizontal line segments and their input content is as follows. overlap_len(i,j) is the overlapping length of line i and line j. The total overlapping length for these four line segments is: overlap_len(1,2)+ overlap_len(1,3)+ overlap_len(2,3)=45+155+20=220. Notably, the overlapping length between lines 1 and 4 is 0.

Output

Please print out the total overlapping length of the line set. Since the total overlapping length may exceed the maximum value of a 32bits integer, please use a larger integer number n (n < 263) to output your result. Follow the format of the sample output.