\(A\) の各要素を \((A_i, i)\) の辞書順で順序付けるとしてよいです．これにより，大小関係の順序が一意に定まります．

\(A_i\) が最大値になるような連続部分列について，\(A_i\) より左の要素数を \(l\)，右の要素数を \(r\) として，\((l, r)\) が満たすべき条件について考えます．

\(A_i\) よりも小さい要素が \(A_i\) のすぐ左にいくつ連続するかを \(L_i\) とします．右についても同様に \(R_i\) とします(これらの値の求め方は後述します)．

このとき，\(0 \leq l \leq L_i,\ 0 \leq r \leq R_i\) を満たすとき，またその時に限り，\((l, r)\) に対応する連続部分列は \(A_i\) を最大値として持ちます．

ここで，\(x_{min} := \min(l, r),\ x_{max} := \max(l, r)\) とおくと，\(A_i\) の \(ans\) への寄与は以下のように表せます．

• \(0 < k \leq 1 + x_{min}\) について，\(ans[k]\) に \(k \times A_i\) を加える
• \(1 + x_{min} < k \leq 1+x_{max}\) について，\(ans[k]\) に \((1 + x_{min}) \times A_i\) を加える
• \(1+x_{max} < k \leq 1 + x_{min} + x_{max}\) について，\(ans[k]\) に \((2 + x_{min} + x_{max} - k) \times A_i\) を加える

これらはすべて傾きが一定の一次関数です．

ある範囲に定数を加えることを再現するには imos 法と呼ばれるテクニックが適用できました． これを以下のように応用することで，上述の範囲加算を再現することが可能です．

まずは範囲加算を以下のように置き換えます．

• \(ans^{(2)}[1]\) に \(+A_i\) を加える
• \(ans^{(2)}[2 + x_{min}]\) に \(-A_i\) を
• \(ans^{(2)}[2 + x_{max}]\) に \(-A_i\) を加える
• \(ans^{(2)}[3 + x_{min} + x_{max}]\) に \(+A_i\) を加える

そして，すべての範囲加算を終えた後，以下のようにして累積和を \(2\) 回繰り返します．

• \(ans^{(1)}[0] = ans^{(2)}[0]\)，\(ans^{(1)}[i+1] := ans^{(1)}[i] + ans^{(2)}[i+1]\) とする
• \(ans[0] = ans^{(1)}[0]\)，\(ans[i+1] := ans[i] + ans^{(1)}[i+1]\) とする

これによって，\(ans\) を求めることができます．

\(L_i, R_i\) の値の求め方

既に見た添え字の集合 \(S\) を \(\{0, N+1\}\) で初期化します．

\(A_i\) を大きい順に見ていって，以下のように操作します．

1. \(S\) の要素のうち \(i\) より小さい最大値を \(L'\)，大きい最小値を \(R'\) とする．
2. \(L_i = i - L' - 1\), \(R_i = R' - i - 1\) とする．
3. \(S\) に \(i\) を追加する．

操作のうち 1. にあたる部分は，C++ であれば標準ライブラリにある std::set を利用し，set.lower_bound 関数を駆使することで実現可能です．

C++ での実装例を以下に示します。

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <array>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::string;
using std::pair;
using std::vector;
using std::set;
using std::min;
using std::max;
using std::array;
#include <atcoder/all>


typedef long long ll;
typedef pair<ll, ll> P;

vector<ll> solve (const ll n, const vector<ll> &a) {
	vector<ll> ans(n+1, 0);

	vector<P> asort(n);
	for (ll i = 0; i < n; i++) {
		asort[i] = {a[i], i};
	}
	sort(asort.begin(), asort.end());

	array<vector<ll>, 3> integral;

	integral[0].resize(n+3);
	for (ll i = 0; i <= n+2; i++) {
		integral[0][i] = 0;
	}
	set<ll> used = {-1, n};
	for (ll i = n-1; i >= 0; i--) {
		ll val = asort[i].first;
		ll idx = asort[i].second;

		auto itgeq = used.lower_bound(idx);
		auto itle = itgeq; --itle;

		// how many elements (on left/right) can a[idx] absorb as a maximum
		ll r = *itgeq - idx - 1;
		ll l = idx - *itle - 1;

		ll xmin = min(l, r), xmax = max(l, r);

		// ans[0 < i <= 1+min] <- i
		// ans[1+min < i <= 1+max] <- 1+min
		// ans[1+max < i <= 1+min+max] <- 1+min - (i - (1+max))
		// ans[1+min+max < i] <- 0

		// ans'[0 < i <= 1+min] <- +1
		// ans'[1+min < i <= 1+max] <- 0
		// ans'[1+max < i <= 1+min+max] <- -1
		// ans'[1+min+max < i] <- 0

		// ans''[1] <- +1
		// ans''[1+min+1] <- -1
		// ans''[1+max+1] <- -1
		// ans''[1+min+max+1] <- +1
		integral[0][1            ] += val * (+1);
		integral[0][1+xmin+1     ] += val * (-1);
		integral[0][1+xmax+1     ] += val * (-1);
		integral[0][1+xmin+xmax+2] += val * (+1);

		used.insert(idx);
	}
	for (ll order = 1; order <= 2; order++) {
		integral[order].resize(n+3);
		integral[order][0] = 0;
		for (ll i = 1; i <= n+2; i++) {
			integral[order][i] = integral[order][i-1] + integral[order-1][i];
		}
	}

	for (ll i = 1; i <= n; i++) {
		ans[i] = integral[2][i];
	}


	return ans;
}


int main (void) {
	ll n;
	cin >> n;
	vector<ll> a(n);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<ll> anslist = solve(n, a);
	for (ll i = 1; i <= n; i++) {
		cout << anslist[i] << "\n";
	}


	return 0;
}