2023-03-01 16:50:41
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
return x;
}
ll n;
ll f[400005],a[400005];
vector<ll>S;
int main(){
n=read();
for(ll i=1;i<=n;i++){
a[i]=read();
}
memset(f,0x3f,sizeof(f));
f[1]=0;
ll sqrtn=sqrtl(n);
//先放个1，1号一定是单调的()
S.push_back(1);
printf("%lld",f[1]);
for(ll i=2;i<=n;i++){
ll minn=a[i];
// minn>sqrtn
//原因是此时满足j-i<=sqrtn才能最优
//证明就是i->j最大值为(j-i)*n
//那么min(...)*(i-j)^2<=(j-i)*n
//min(...)*(j-i)<=n
//若min(...)>=sqrtn可以得到(j-i)<=sqrtn
//此时可以过滤掉一个根号，加快速度
//但不需要特判，属于必要性先行
//思路：为了省一个根号复杂度
for(ll k=i-1;k>=max(1ll,i-sqrtn);--k){
f[i]=min(f[i],f[k]+(minn=min(minn,a[k]))*(i-k)*(i-k));
}
//minn<=sqrtn
//此时上面的方法不好用了，如果强行n^2会炸
//又有性质i->j最小时，满足min(...)==a[i] or a[j]
//用反证法结合(a+b)^2>=a^2+b^2可以证明(具体见https://www.luogu.com.cn/blog/explodingkonjac/solution-cf1768f)
//case1 min(...)==a[j](j->i)
//找i前面满足(j,i)内a[j]最小的值<=sqrt的(不然就是第一种情况了),满足单调性质(相同的话后面比前面优)
//此时可以使得栈内个数小于sqrt(n)
//用单调栈维护（实际是vector，好便利，而且与栈有相似功能）
//思路：最小值边缘时的特殊性质
for(ll j:S){
f[i]=min(f[i],f[j]+(i-j)*(i-j)*a[j]);
}
//case2 min(..)==a[i](i->j)
//直接暴力即可，大于时退出（维护单调）
if(a[i]<=sqrtn){
for(ll j=i-1;j;--j){
if(a[i]>=a[j])break;
f[i]=min(f[i],f[j]+(i-j)*(i-j)*a[i]);
}
while(!S.empty()&&a[i]<=a[S.back()])S.pop_back();
S.push_back(i);
}
printf(" %lld",f[i]);
}
}