题目描述

Geo 三世国王的陵墓是一座巨大的石质建筑，形状是一张直方图。这里的直方图指一个简单的正交多边形，它的边界由两条链组成：上边界是一条关于水平轴单调的折线，下边界是一条水平线段，称为基底线段。

一个直方图形状的陵墓、外部点 $S$、内部宝藏点 $T$，以及从 $S$ 经过边界顶点 $a,b,c$ 到达 $T$ 的若干候选路径。图中应标出坐标网格和顶点名称，这是样例 1 对应该图。

传说陵墓内部藏着宝藏。著名寻宝者 Metry 已经确定宝藏位于点 $T$。她会从陵墓外部的某个点 $S$ 出发，用设备在陵墓边界上的一个顶点处钻入，然后进入内部取走宝藏。

设备只能在边界顶点处钻入，而且只能钻入一次。由于在任意顶点钻墙所需时间相同，需要最小化的是从 $S$ 到 $T$ 的路径长度，其中路径必须经过恰好一个陵墓边界顶点。

例如，原图中经过顶点 $a$ 的路径长度为

经过顶点 $b$ 的路径长度为

经过顶点 $c$ 的路径长度为

其中最短路径经过顶点 $b$。

给定陵墓边界以及点 $S,T$ 的位置，请求出从 $S$ 到 $T$ 且只在一个边界顶点处穿过陵墓边界的最短路径长度。

输入格式

第一行包含一个整数 $n$，表示描述陵墓直方图的顶点数量。保证 $n$ 为偶数。

第二行包含 $n$ 个整数 $v_1,v_2,\ldots,v_n$，其中 $v_1=v_n=0$。这些数依次表示沿直方图上边界从基底线段左端走到右端时，竖直边的 $x$ 坐标和水平边的 $y$ 坐标。竖直边和水平边交替出现。每条边长度至少为 $1$，并且所有 $x$ 坐标严格递增。

最后一行包含四个整数 $s_x,s_y,t_x,t_y$，其中 $(s_x,s_y)$ 表示点 $S$，$(t_x,t_y)$ 表示点 $T$。保证 $S$ 在直方图外部，$T$ 在直方图内部，且二者都不在边界上。

输出格式

输出一行一个实数，表示从 $S$ 到 $T$ 的最短路径长度。

输出值必须包含整数部分、小数点和小数部分。若你的输出 $z$ 满足

其中 $a$ 为标准答案，则会被判为正确。

两点 $p=(x_1,y_1)$ 和 $q=(x_2,y_2)$ 的欧几里得距离为

数据范围

• $4\le n\le 100000$；
• $n$ 为偶数；
• $v_1=v_n=0$；
• $0\le v_i\le 10^6$；
• $-10^6\le s_x,s_y\le 2\cdot 10^6$；
• $0<t_x,t_y<10^6$。

样例 1

输入

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

输出

10.077687

样例 2

输入

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

输出

11.767829

样例 3

输入

4
0 5 8 0
8 6 4 2

输出

6.0