Transition Year 2. The Bridges Return#1799
A disaster has struck the land of Coordinatia! The evil witch Bastinda, having learned that travelers could easily go from city A to city B, sent a tornado across the land, destroying all bridges over the rivers. The King of Coordinatia, His Majesty Gurig VIII, was deeply troubled and ordered his bridge builders to construct new bridges over the rivers (possibly at new locations). However, knowing how vital the path from A to B is for travelers, they were instructed to make this route as short as possible.
In Coordinatia, all rivers flow strictly parallel to the -axis (), and all bridges are built strictly perpendicular to the rivers' flow (that is, parallel to the -axis, ).
Write a program to determine the minimum possible length of the path from city A to city B, assuming optimal bridge placement.
The first line contains a single integer (1 \leq N \leq 100\,000), the number of rivers.
Each of the next lines contains two integers a_i and b_i, describing the banks of the rivers (the right bank is the line y = a_i and the left bank is y = b_i, with -10^6 \leq a_i < b_i \leq 10^6).
The next two lines contain the coordinates x_A, y_A of city and x_B, y_B of city , respectively. These coordinates are also integers in the range [-10^6, 10^6].
It is guaranteed that no two rivers overlap and that cities and are located on dry land.
Output a single number: the minimum possible length of the path from to , with a precision of at least 10^{-5}.
Example 1