【牛客练习赛72】C

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0)
#define local freopen("in.text","r",stdin)
#define pi acos(-1)
const int mo=1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
ll qp(ll a,ll b){if(a==0) return 0;ll res=1;a%=mo;for(;b;b>>=1){if(b&1)res=res*a%mo;a=a*a%mo;}return res;}
template<class T> bool read(T & ret)//ll,int,double,float,+/-
{
	char c;int sgn;T bit=0.1;if(c=getchar(),c==EOF) return 0;while(c!='-' && c!='.' && (c<'0' || c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0' && c<='9') ret=ret*10+(c-'0');if(c==' '||c=='\n') {ret*=sgn;return 1;}while(c=getchar(),c>='0' && c<='9') ret+=(c-'0')*bit,bit/=10;ret*=sgn;return 1;
}

int n;
double a[1000010];
int s[1000010];

bool check(int x,int y,int z)
{
    return (a[y]-a[x])/(y-x) > (a[z]-a[x])/(z-x);
}
signed main(){
	read(n);
    int top=0;
	for(int i=1;i<=n;++i) read(a[i]);
    for(int i=1;i<=n;++i)
    {
        while(top>=2&&check(s[top-1],s[top],i)) top--;
        s[++top] = i;
    }

	long double ans=0;
    for(int i=2;i<=top;++i)
    {
        ans+=(a[s[i]] + a[s[i-1]])*(s[i]-s[i-1]+1)/2.0;
    }
    for(int i=2;i<=top-1;++i) ans-=a[s[i]];
	cout<<fixed<<setprecision(10)<<ans<<endl;
	
	return 0;
}