Mauzoleum King Geo III jest ogromną kamienną budowlą w kształcie histogramu. Histogram to prosty wielokąt prostokątny, którego brzeg składa się z dwóch łańcuchów: górnego, monotonicznego względem osi poziomej, oraz dolnego, będącego poziomym odcinkiem zwanym podstawą (patrz rysunek E.1).

Rysunek E.1: Mauzoleum i kilka ścieżek między $S$ a $T$

Podobno gdzieś w mauzoleum ukryty jest skarb. Metry, znana poszukiwaczka skarbów, odkryła jego położenie w punkcie $T$. Planuje przebić ściany mauzoleum, wejść do środka i zabrać skarb. Rozpocznie w ustalonym miejscu $S$ poza mauzoleum. Jej sprzęt pozwala przewiercić tylko jeden punkt odpowiadający wierzchołkowi brzegu mauzoleum. Ponieważ czas wiercenia ścian jest taki sam przy każdym wierzchołku, kluczem do minimalizacji czasu jest znalezienie najkrótszej ścieżki z $S$ do $T$.

Rysunek E.1 pokazuje mauzoleum oraz kilka możliwych ścieżek z $S$ do $T$, przy których wierzchołki przebija się tylko raz. Ścieżka przez wierzchołek $a$ ma długość $11.385165=6+\sqrt{29}$, przez wierzchołek $b$ długość $10.077687=\sqrt{20}+\sqrt{13}+2$, a przez wierzchołek $c$ długość $11.0=2+\sqrt{25}+4$. Spośród nich najkrótsza jest ścieżka przez wierzchołek $b$.

Dla danego brzegu mauzoleum oraz położeń $S$ i $T$ napisz program znajdujący długość najkrótszej ścieżki z $S$ do $T$ z pojedynczym przebiciem wierzchołka.

Wejście

Program ma czytać ze standardowego wejścia. Wejście zaczyna się wierszem zawierającym liczbę całkowitą $n$ ($4\le n\le100000$), gdzie $n$ jest parzyste i oznacza liczbę wierzchołków histogramu przedstawiającego mauzoleum. Drugi wiersz zawiera $n$ liczb całkowitych $v_1,v_2,\ldots,v_n$ ($v_1=v_n=0$, $0\le v_i\le10^6$), które oznaczają współrzędne $x$ krawędzi pionowych i współrzędne $y$ krawędzi poziomych. Krawędzie pionowe i poziome występują naprzemiennie podczas przechodzenia górnym łańcuchem histogramu od lewego końca podstawy do prawego. Długość każdej krawędzi wynosi co najmniej $1$, a współrzędne $x$ są podane w porządku ściśle rosnącym. Ostatni wiersz zawiera cztery liczby całkowite $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$), gdzie $(s_x,s_y)$ i $(t_x,t_y)$ odpowiadają odpowiednio punktom $S$ i $T$. Zauważ, że $S$ leży poza histogramem, a $T$ wewnątrz niego, i żaden z nich nie leży na brzegu.

Wyjście

Program ma pisać na standardowe wyjście. Wypisz dokładnie jeden wiersz zawierający dokładnie jedną liczbę rzeczywistą równą długości najkrótszej ścieżki między $S$ a $T$. Twoja odpowiedź $z$ powinna składać się z części całkowitej, kropki dziesiętnej i części ułamkowej. Zostanie uznana za poprawną, jeśli $a-10^{-3}<z<a+10^{-3}$, gdzie $a$ oznacza odpowiedź jury. Odległość euklidesowa między punktami $p=(x_1,y_1)$ i $q=(x_2,y_2)$ wynosi $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.

Poniżej podano przykładowe wejście i wyjście dla trzech przypadków testowych. (Przykładowe wejście 1 odpowiada rysunkowi E.1.)

Przykład

Wejście 1

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

Wyjście 1

10.077687

Wejście 2

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

Wyjście 2

11.767829

Wejście 3

4
0 5 8 0
8 6 4 2

Wyjście 3

6.0