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