King Geo III の霊廟は、ヒストグラムの形をした巨大な石造建築物である。ヒストグラムとは、境界が二つの鎖からなる単純な直交多角形である。上側の鎖は水平軸に関して単調であり、下側の鎖は底辺と呼ばれる水平な線分である（図E.1参照）。

図E.1：霊廟と $S$、$T$ 間のいくつかの経路

霊廟のどこかに宝が隠されているという噂がある。著名なトレジャーハンター Metry は、宝が点 $T$ にあることを突き止めた。Metry は霊廟の壁を破って入り、宝を持ち帰る計画を立てている。彼女は霊廟の外の特定の位置 $S$ から出発する。Metry は装備を使って、霊廟の境界の頂点に対応する一点だけを掘削できる。壁を掘削する時間はどの頂点でも同じなので、所要時間を最小にする鍵は $S$ から $T$ までの最短経路を見つけることである。

図E.1は霊廟と、頂点を一度だけ貫通する $S$ から $T$ までのいくつかの経路を示す。頂点 $a$ を通る経路の全長は $11.385165=6+\sqrt{29}$、頂点 $b$ を通る経路の長さは $10.077687=\sqrt{20}+\sqrt{13}+2$、頂点 $c$ を通る経路の長さは $11.0=2+\sqrt{25}+4$ である。このうち最短なのは頂点 $b$ を通る経路である。

霊廟の境界と $S$、$T$ の位置が与えられる。頂点を一度だけ貫通する $S$ から $T$ までの最短経路の長さを求めるプログラムを作成せよ。

入力

プログラムは標準入力から読み込む。入力は整数 $n$（$4\le n\le100000$）を含む行で始まる。$n$ は偶数であり、霊廟を表すヒストグラムの頂点数である。二行目には $n$ 個の整数 $v_1,v_2,\ldots,v_n$（$v_1=v_n=0$, $0\le v_i\le10^6$）が与えられ、垂直な辺の $x$ 座標と水平な辺の $y$ 座標を表す。ヒストグラムの上側の鎖を底辺の左端から右端へたどると、垂直な辺と水平な辺が交互に現れる。各辺の長さは少なくとも $1$ であり、$x$ 座標は狭義単調増加の順で与えられる。最後の行には四つの整数 $s_x,s_y,t_x,t_y$（$-10^6\le s_x,s_y\le2\times10^6$, $0<t_x,t_y<10^6$）が含まれ、$(s_x,s_y)$ と $(t_x,t_y)$ はそれぞれ点 $S$ と $T$ に対応する。$S$ はヒストグラムの外部、$T$ は内部にあり、どちらも境界上にはないことに注意せよ。

出力

プログラムは標準出力に書き込む。ちょうど一行を出力する。この行には $S$ と $T$ の間の最短経路の長さである実数をちょうど一つ含める。出力 $z$ は整数部、小数点、小数部からなる形式でなければならない。審査員の答えを $a$ とすると、$a-10^{-3}<z<a+10^{-3}$ を満たす場合に正解と判定される。二点 $p=(x_1,y_1)$ と $q=(x_2,y_2)$ のユークリッド距離は $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ である。

以下に三つのテストケースの入力例と出力例を示す。（入力例1は図E.1に対応する。）

入出力例

入力 1

12
0 5 2 8 5 3 7 6 11 4 13 0
11 8 3 3

出力 1

10.077687

入力 2

8
0 7 2 2 5 7 7 0
-2 4 6 4

出力 2

11.767829

入力 3

4
0 5 8 0
8 6 4 2

出力 3

6.0