El mausoleo de King Geo III es una enorme estructura de piedra con forma de histograma. Un histograma es un polígono rectilíneo simple cuya frontera consta de dos cadenas: una superior que es monótona respecto al eje horizontal, y una inferior que es un segmento horizontal llamado segmento base (véase la figura E.1).

Figura E.1: Un mausoleo y varios caminos entre $S$ y $T$

Se rumorea que hay un tesoro escondido en algún lugar de este mausoleo. Metry, una famosa cazadora de tesoros, ha descubierto que está en el punto $T$. Su plan es perforar las paredes del mausoleo, entrar y recuperar el tesoro. Comenzará en una ubicación específica $S$ fuera del mausoleo. Con su equipo, Metry puede perforar solo un punto, que corresponde a un vértice de la frontera del mausoleo. Como el tiempo necesario para perforar las paredes es el mismo en todos los vértices, la clave para minimizar el tiempo empleado es encontrar el camino más corto de $S$ a $T$.

La figura E.1 muestra un mausoleo junto con varios caminos posibles de $S$ a $T$, perforando vértices una sola vez. El camino por el vértice $a$ tiene una longitud total de $11.385165=6+\sqrt{29}$, el camino por el vértice $b$ mide $10.077687=\sqrt{20}+\sqrt{13}+2$, y el camino por el vértice $c$ mide $11.0=2+\sqrt{25}+4$. Entre ellos, el más corto pasa por el vértice $b$.

Dadas la frontera del mausoleo y las posiciones de $S$ y $T$, escribe un programa para encontrar la longitud del camino más corto de $S$ a $T$ con una única perforación en un vértice.

Entrada

Tu programa debe leer de la entrada estándar. La entrada empieza con una línea que contiene un entero $n$ ($4\le n\le100000$), donde $n$ es par y es el número de vértices del histograma que representa el mausoleo. En la segunda línea se dan $n$ enteros $v_1,v_2,\ldots,v_n$ ($v_1=v_n=0$, $0\le v_i\le10^6$), que representan las coordenadas $x$ de las aristas verticales y las coordenadas $y$ de las horizontales. Las aristas verticales y horizontales se alternan al recorrer la cadena superior del histograma desde el extremo izquierdo hasta el derecho del segmento base. Cada arista tiene longitud al menos $1$, y las coordenadas $x$ se dan en orden estrictamente creciente. La última línea contiene cuatro enteros $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$), donde $(s_x,s_y)$ y $(t_x,t_y)$ corresponden a los puntos $S$ y $T$, respectivamente. Observa que $S$ está fuera del histograma y $T$ está dentro, y ninguno de ellos está en la frontera.

Salida

Tu programa debe escribir en la salida estándar. Imprime exactamente una línea que contenga exactamente un valor real: la longitud del camino más corto entre $S$ y $T$. Tu salida $z$ debe tener un formato formado por su parte entera, un punto decimal y su parte fraccionaria. Se considerará correcta si cumple $a-10^{-3}<z<a+10^{-3}$, donde $a$ denota la respuesta del jurado. La distancia euclídea entre dos puntos $p=(x_1,y_1)$ y $q=(x_2,y_2)$ es $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.

A continuación se muestran la entrada y la salida de ejemplo para tres casos de prueba. (La entrada de ejemplo 1 corresponde a la figura E.1.)

Ejemplos

Entrada 1

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

Salida 1

10.077687

Entrada 2

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

Salida 2

11.767829

Entrada 3

4
0 5 8 0
8 6 4 2

Salida 3

6.0