問題文

高橋君は、レーシングゲームをプレイしようとしています。
レースは $(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$ 座標が空白を区切りとして与えられる。

• 続く $3$ 行目から $N+2$ 行目の各行には、$i+3$ 行目に$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$ を満たす。

出力

レースの最短経路を $1$ 行で出力せよ。
なお、出力は絶対誤差または相対誤差 $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

Source Name

ARC 001