AT_arc001_4.[ARC001D] レースゲーム

高桥正在尝试玩赛车游戏。 比赛从 $(x,y)=(start,0)$ 处开始，向 $(x,y)=(goal,N)$ 处的目标前进。

对于 $0 \le y \le n$，我们给出了路径的左端和右端，这条路径就是依次连接这些区间两端的直线的内侧。

上图为输入 1 示例。红圈为起点，蓝圈为终点， 棕色区域为赛道。

赛车不能在赛道以外的任何地方行驶。此外，汽车能够在瞬间改变方向，而且汽车的宽度和长度必须可以忽略不计。

高桥希望找到从起点到目标的最短路径，从而征服这款赛车游戏。

第一行是比赛的总长度 $N$。

第二行给出赛道起点和终点的坐标，中间用空格隔开。

从第 $3$ 行到 $N+2$ 行的每一行中，第 $i+3$ 行给出了 $y=i$ 的最左边 $l_i$ 和最右边 $r_i$，中间用空格隔开。

一行输出比赛的最短路径。

请注意，输出结果的绝对误差或相对误差不能大于 $1e-9$。

样例 1 解释

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

• N 为整数，满足 $1 \le N \le 200,000$。

• $l_i$ 和 $r_i$ 为整数，满足 $0 \le li < ri \le 1,000,000$。

• $start$ 是整数，满足 $l_0 \le start \le r_0$。

• $goal$ 是整数，且满足 $l_N \le goal \le r_N$。