问题文

高桥君想要玩赛车游戏。比赛从起点 $(x, y) = (start, 0)$ 开始，向着终点 $(x, y) = (goal, N)$ 前进。对于 $0 ≦ k ≦ N$ 中的 $y=k$，给出了赛道的左端和右端，将它们依次连接起来形成的线段内部就是赛道。

图示：示例输入1。红色圆圈为起点，蓝色圆圈为终点，棕色部分为赛道。

赛车只能在赛道上行驶，不能离开赛道。并且假设可以瞬间改变方向，忽略车辆的宽度和长度。高桥君想要找到从起点到终点的最短路径以攻略这个赛车游戏。

输入

输入的格式如下：$N$ $start$ $goal$ $l_0$ $r_0$ $l_1$ $r_1$ $:$ $:$ $l_N$ $r_N$

• 第1行给出了赛道的总长度 $N$。
• 第2行给出了赛道的起点坐标 $start$ 和终点坐标 $goal$。
• 接下来的 $N+1$ 行中，第 $i+2$ 行给出了 $y=i$ 的赛道的左端 $l_i$ 和右端 $r_i$。

此外，输入满足以下条件：

• $N$ 是一个整数，满足 $1 ≦ N ≦ 200,000$。
• $l_i$ 和 $r_i$ 是整数，满足 $0 ≦ l_i ＜ r_i ≦ 1,000,000$。
• $start$ 是一个整数，满足 $l_0 ≦ start ≦ r_0$。
• $goal$ 是一个整数，满足 $l_N ≦ goal ≦ r_N$。

输出

以一行输出赛车的最短路径。允许绝对误差或相对误差不超过 $1e-9$。

输入例子1

7
3 3
2 5
4 6
2 3
3 6
3 4
4 6
2 5
1 5

输出例子1

8.22677276241436

红色圆圈为起点，蓝色圆圈为终点，下图中的红线是最短路径。

输入例子2

5
3 3
0 5
0 5
0 5
0 5
0 5
0 5

输出例子2

5

数据来源：ARC 001