Solution

对于任意一组我们可以使其中间的数与之构成一个等差数列，利用数形结合，使每个数的，，这在几何学上就是一个凸壳。
问题转换为求一个凸壳并计算答案。

凸壳需要满足：
对于任意三个点，，由于除法有精度误差，上式转换为乘法。


若不满足上述条件则点需要删除。

最后对维护之后的凸壳进行等差数列求和即可，需要注意的是第到第个端点重复计算，需要减去。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod  = 1e9 + 7;
const ll N = 1e6 + 5;

int n;
ll a[N],b[N],top;
double ans;

bool check(int x,int y,int z){
    return (a[z]-a[x])*(y-x)-(a[y]-a[x])*(z-x)<0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(10);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        while(top>=2 && check(b[top-1], b[top], i)) top--;
        b[++top]=i;
    }
    for(int i=2;i<=top;i++) ans+=(a[b[i-1]]+a[b[i]])*(b[i]-b[i-1]+1)/2.0;
    for(int i=2;i<=top-1;i++) ans-=a[b[i]];
    cout<<ans<<'\n';
    return 0;
}