小红的悬崖
题号:NC266615
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

小红在 vp 牛客小白月赛的时候做到了一道题《悬崖》,深受震撼,于是她也准备出一道悬崖题。

众所周知,悬崖也不一定是笔直向下的。现在通过若干点来描述悬崖的关键点,用于表示悬崖的形状。相邻关键点的连线为崖面,左侧为岩石,右侧为深渊。请你求出小红从崖顶前往崖底的最小距离。

注:小红是魔法少女,可以在空中飞行,但不能穿过岩石。

输入描述:

第一行输入一个正整数n,代表悬崖的高度。
第二行输入n+1个正整数:a_0,a_1,...,a_n,分别代表关键点坐标(a_i,i)
1\leq n,a_i \leq 10^5

输出描述:

一个浮点数,代表小红行走的最小距离。你需要保证和正确答案的相对误差不超过10^-7才能通过本题。
示例1

输入

复制
4
7 6 8 4 6

输出

复制
5.064495102246

说明

如下图,悬崖的 5 个关键点为:(7,0),(6,1),(8,2),(4,3),(6,4)
小红初始在 (6,4) 点,她直接通过直线飞行到 (8,2) 点,再通过直线飞行到 (7,0) 点,这样的路程是最短的。