Lifeguards (Silver)#10420
Farmer John has opened a swimming pool for his cows, figuring it will help them relax and produce more milk.
To ensure safety, he hires cows as lifeguards, each of which has a shift covering a contiguous interval of time during the day. For simplicity, the pool is open daily from time t = 0 until time t = 10^9, so each shift can be described by two integers: the times at which a cow starts and ends her shift. For example, a lifeguard starting at time t = 4 and ending at time t = 7 covers three units of time (note that the endpoints are "points" in time).
Unfortunately, Farmer John has hired one more lifeguard than he can afford. Given that he must fire exactly one lifeguard, what is the maximum amount of time that can still be covered by the shifts of the remaining lifeguards? An interval of time is covered if at least one lifeguard is present.
The first line contains an integer n~(1 \le n \le 10^5). Each of the next lines describes a lifeguard by two integers in the range from to 10^9: the starting and ending times of that lifeguard's shift. All these endpoints are distinct. Shifts of different lifeguards may overlap.
Print one integer: the maximum amount of time that can still be covered if Farmer John fires one lifeguard.
Example 1