A logging service records busy periods as half-open segments [start, end) on an integer timeline. Because periods can overlap, you want the total amount of time that is busy at all: the length of the union of the segments. A point is counted once no matter how many segments cover it.
Formally, output the measure of the set of real numbers x such that start <= x < end for at least one segment.
Input format
Line 1: an integer n — the number of segments.
Next n lines: two integers start end describing one segment [start, end).
Output format
A single integer: the total length of the union of all segments.
Constraints
- 1 <= n <= 100000
- -1000000000 <= start < end <= 1000000000
- Segments may overlap, touch, be nested, or be identical.