神仙题，被教育了。

观察性质的能力不足，需要改进。

DP 比较显然，

要做这题，首先要注意到 这个条件，并猜测这个条件有蹊跷（我当时看到了也没管）。

如果我们想一步跳多个格子，会耗费 的代价

但我们肯定有一种策略就是一步一步跳过去，耗费 的代价，其上界为 。

所以从 能转移到 的前提条件是 。

可以得到 。

那么这里就一定有一项

分类讨论：

1. ，这一部分可以暴力转移，时间复杂度

2. 这个时候只靠上面的观察就不够了，我们还需继续发现性质。

   考察三个数 ，如果说 ，那我直接从 跳到 ，显然是不如从 跳到 ，再从 跳到 更优的。因为这三次跳跃的 都是 ，而 是显然的。

   所以 能转移到 还必须满足对于所有 ，都有 ，也就是说 或 。

   继续分类讨论：

   1. ，我们维护一个从栈顶向栈底严格递减的单调栈，此时 显然是单调栈中的元素，因为 ，我们在维护单调栈时只需要把 的元素入栈即可。而单调栈中的元素互不相同，所以单调栈的长度显然不会超过 。因此，暴力枚举单调栈中的每个元素转移即可。

   2. ，我们可以往前找到第一个 的元素 ，在 中的 都可以转移过来，我们暴力枚举这样的 转移即可。

      接下来证明这一部分的时间复杂度： 设 表示最大的 满足 ，那么 ，即 。

      把 相同的所有元素一起考虑 ，其 之和显然是 的。

      因为这里只考虑 的 ，所以 被考虑到的所有 的总和都是 的，那 之和自然也是 的。

综上所述，我们在 的时间复杂度内解决了本题。

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
typedef long long ll;
template<typename T> inline void ckmin(T &x,const T &y) { if(x > y) x = y;}
int n;
int a[N];
ll dp[N];
int stk[N],top;
int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i];
	int lim = sqrt(n) + 0.5;
	dp[1] = 0;stk[top = 1] = 1;
	for(int i = 2;i <= n;i++)
	{
		dp[i] = 1e18;
		for(int l = 1,mn = a[i];l <= min(i - 1,lim + 1);l++)
			mn = min(mn,a[i - l]),
			ckmin(dp[i],dp[i - l] + 1ll * l * l * mn);
		for(int j = 1;j <= top;j++)
			if(a[stk[j]] <= a[i])
			ckmin(dp[i],dp[stk[j]] + 1ll * (i - stk[j]) * (i - stk[j]) * a[stk[j]]);
		if(a[i] <= lim)
		{
			for(int j = i - 1;j >= 1;j--)
			{
				if(a[j] <= a[i]) break;
				ckmin(dp[i],dp[j] + 1ll * (i - j) * (i - j) * a[i]);
			}
			while(top && a[stk[top]] >= a[i]) --top;
			stk[++top] = i;
		}
	}
	for(int i = 1;i <= n;i++) printf("%lld ",dp[i]);printf("\n");
	return 0;
}