#include #include #include #define LD long double #define LL long long #define Re register int #define S2(a) (1ll*(a)*(a)) using namespace std; const LL N=1e5+3,inf=1e18; int n,H[N],W[N],Q[N];LL S[N],dp[N]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } //dp[i]=min(dp[i],dp[j]+(H[i]-H[j])*(H[i]-H[j])+S[i-1]-S[j]); //dp[i]=dp[j]-2*H[i]*H[j]+H[j]*H[j]+H[i]*H[i]+S[i-1]-S[j] //(2*H[i]) * H[j] + (dp[i]-S[i-1]-H[i]*H[i]) = (dp[j]+H[j]*H[j]-S[j]) // k * x + b = y #define X(j) (a[j].x) #define Y(j) (a[j].y) struct QAQ{ int k,x,id;LL y; inline bool operator<(const QAQ &O)const{return x!=O.x?xY(i)?inf:-inf):(LD)(Y(j)-Y(i))/(X(j)-X(i));} inline void CDQ(Re L,Re R){ if(L==R){Re j=a[L].id;a[L].y=dp[j]+(LL)H[j]*H[j]-S[j];return;} Re mid=L+R>>1,p1=L,p2=mid+1,h=1,t=0; for(Re i=L;i<=R;++i)a[i].id<=mid?b[p1++]=a[i]:b[p2++]=a[i]; for(Re i=L;i<=R;++i)a[i]=b[i]; CDQ(L,mid); for(Re i=L;i<=mid;++i){ while(h=slope(Q[t-1],i))--t; Q[++t]=i; } for(Re i=mid+1,j,id;i<=R;++i){ while(h