Total Covered Length

Difficulty: 1400 3000 ms 128 MB

intervals sorting

Print the total length of the union of all intervals [a, b] (measure, so [1,3] and [2,5] cover 4).

Input: the first line has N; the next N lines each have two integers a b (a ≤ b).

Output: the total covered length.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ a ≤ b ≤ 10⁶

Sample Tests

2
1 3
2 5

4

2
1 2
5 6

2

Read the Editorial