#include <bits/stdc++.h>
using namespace std;

template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }

using ll = int64_t;
using uint = uint32_t;
using ull = uint64_t;

template <class T> using vc = vector<T>;
template <class T> using vvc = vector<vector<T>>;

using vi = vector<int>;

template <class N> struct seglazy {
#define fa forward<A>(args)...
	/// start-hash
	vc<N> x;
	int n, log, s;
	seglazy() {}
	template <class T> seglazy(const vc<T>& a){
		n = int(a.size());
		log = 0;
		while ((1 << log) < n) log++;
		s = 1 << log;
		x.resize(2*s);
		for (int i = 0; i < n; i++) x[s+i] = N(a[i]);
		for (int i = s-1; i >= 1; i--) upd(i);
	}
	/// end-hash

	/// start-hash
	void upd(int i){
		x[i] = N::merge(x[2*i], x[2*i+1]);
	}
	void push(int i) {
		x[i].push(x[2*i], x[2*i+1]);
	}
	/// end-hash

	/// start-hash
	N prod(int l, int r) {
		assert(0 <= l && l <= r && r <= n);
		if (l == r) return N();
		l += s, r += s;
		for (int i = log; i >= 1; i--) {
			if (((l >> i) << i) != l) push(l >> i);
			if (((r >> i) << i) != r) push((r-1) >> i);
		}
		N vl, vr;
		for (int a = l, b = r; a < b; a /= 2, b /= 2) {
			if (a & 1) vl = N::merge(vl, x[a++]);
			if (b & 1) vr = N::merge(x[--b], vr);
		}
		return N::merge(vl, vr);
	}
	/// end-hash

	/// start-hash
	template <class F, class... A>
	void apply(int i, F f, A&&... args) {
		if ((x[i].*f)(fa) || i >= s) return;
		push(i);
		apply(2*i, f, fa);
		apply(2*i+1, f, fa);
		upd(i);
	}
	/// end-hash

	// U: is an update or not
	/// start-hash
	template <bool U = true, class F, class... A>
	void apply(int l, int r, F f, A&&... args) {
		assert(0 <= l && l <= r && r <= n);
		if (l == r) return;
		l += s, r += s;
		for (int i = log; i >= 1; i--) {
			if (((l >> i) << i) != l) push(l >> i);
			if (((r >> i) << i) != r) push((r-1) >> i);
		}

		static int buf[2][30];
		int cnt[2]{};
		for (int a = l, b = r; a < b; a /= 2, b /= 2) {
			if (a & 1) buf[0][cnt[0]++] = a++;
			if (b & 1) buf[1][cnt[1]++] = --b;
		}
		for (int z = 0; z < cnt[0]; z++) apply(buf[0][z], f, fa);
		for (int z = cnt[1]-1; z >= 0; z--) apply(buf[1][z], f, fa);

		if constexpr(U) {
			for (int i = 1; i <= log; i++) {
				if (((l >> i) << i) != l) upd(l >> i);
				if (((r >> i) << i) != r) upd((r-1) >> i);
			}
		}
	}
	/// end-hash

	N all_prod() { return x[1]; }

	/// start-hash
	template <class F, class... A>
	pair<int, N> max_right(int l, F f, A&&... args){
		assert(0 <= l && l <= n);
		if (l == n) return {n, N()};
		l += s;
		for (int i = log; i >= 1; i--) push(l >> i);
		N v;
		assert((v.*f)(fa));
		do {
			while (l % 2 == 0) l /= 2;
			if (!(N::merge(v, x[l]).*f)(fa)) {
				while (l < s) {
					push(l);
					l = 2*l;
					N t = N::merge(v, x[l]);
					if ((t.*f)(fa)) {
						v = t;
						l++;
					}
				}
				return {l-s, v};
			}
			v = N::merge(v, x[l]);
			l++;
		} while ((l & -l) != l);
		return {n, v};
	}
	/// end-hash

	// NOT TESTED
	/// start-hash
	template <class F, class... A> 
	pair<int, N> min_left(int r, F f, A&&... args){
		assert(0 <= r && r <= n);
		if (r == 0) return {0, N()};
		r += s;
		for (int i = log; i >= 1; i--) push((r-1) >> i);
		N v;
		assert((v.*f)(fa));
		do {
			r--;
			while (r > 1 && r % 2) r /= 2;
			if (!(N::merge(x[r], v).*f)(fa)) {
				while (r < s) {
					push(r);
					r = 2*r+1;
					N t = N::merge(x[r], v);
					if ((t.*f)(fa)) {
						v = t;
						r--;
					}
				}
				return {r+1-s, v};
			}
			v = N::merge(x[r], v);
		} while ((r & -r) != r);
		return {0, v};
	}
	/// end-hash

	/// start-hash
	N point_get(int p){
		assert(0 <= p && p < n);
		p += s;
		for (int i = log; i >= 1; i--) push(p >> i);
		return x[p];
	}
	void point_set(int p, const N& t) {
		assert(0 <= p && p < n);
		p += s;
		for (int i = log; i >= 1; i--) push(p >> i);
		x[p] = t;
		for (int i = 1; i <= log; i++) upd(p >> i);
	}
	/// end-hash
#undef fa
};

struct trans_t {
	ll a00, a01, a02;
	ll      a11, a12;
	ll           a22;

	trans_t() {
		a00 = a11 = a22 = 1;
		a01 = a02 = a12 = 0;
	}

	trans_t(bool type, int x = 0) : trans_t() {
		if (!type) {
			// A_i += B_i
			a01 = 1;
		} else {
			// B_i += x
			a12 = x;
		}
	}

	friend trans_t operator * (const trans_t& a, const trans_t& b) {
		trans_t res;
		res.a00 = a.a00 * b.a00;
		res.a01 = a.a00 * b.a01 + a.a01 * b.a11;
		res.a02 = a.a00 * b.a02 + a.a01 * b.a12 + a.a02 * b.a22;
		res.a11 = a.a11 * b.a11;
		res.a12 = a.a11 * b.a12 + a.a12 * b.a22;
		res.a22 = a.a22 * b.a22;
		return res;
	}
};

struct D {
	trans_t trans;

	D() {}
	D(int) {}

	bool apply(const trans_t a) {
		trans = a * trans;
		return true;
	}

	void push(D& l, D& r) {
		l.apply(trans);
		r.apply(trans);
		trans = trans_t();
	}

	static D merge(const D&, const D&) {
		return D();
	}
};

constexpr bool TEST = false;

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	int N;
	if constexpr (!TEST) {
		cin >> N;
	} else {
		N = 2345;
	}

	vector<int> P(N);
	if constexpr (!TEST) {
		for (int& p : P) { cin >> p; p--; }
	} else {
		iota(P.begin(), P.end(), 0);
		shuffle(P.begin(), P.end(), mt);
	}

	auto solve = [&]() -> vector<ll> {
		vector<int> dummy(N, 0);
		seglazy<D> seg(dummy);
		vector<pair<int, int>> stk; stk.reserve(N+1);
		stk.emplace_back(N, N);
		for (int i = N-1; i >= 0; i--) {
			seg.apply(i+1, N, &D::apply, trans_t(true, 1));
			while (true) {
				assert(!stk.empty());
				if (P[i] > stk.back().first) {
					seg.apply(stk.back().second+1, N, &D::apply, trans_t(true, -1));
					stk.pop_back();
				} else {
					break;
				}
			}
			assert(!stk.empty() && P[i] < stk.back().first);
			stk.emplace_back(P[i], i);
			seg.apply(i+1, N, &D::apply, trans_t(false));
		}

		for (int i = 1; i < seg.s; i++) {
			seg.push(i);
		}
		assert(N == seg.n);
		vector<ll> res(N);
		for (int i = 0; i < N; i++) {
			res[i] = seg.x[seg.s+i].trans.a02;
		}
		return res;
	};
	auto solve_naive = [&]() -> vector<ll> {
		vector<pair<int, int>> stk; stk.reserve(N+1);
		stk.emplace_back(N, N);
		vector<ll> A(N), B(N);
		for (int i = N-1; i >= 0; i--) {
			for (int j = i+1; j < N; j++) {
				B[j]++;
			}
			while (true) {
				assert(!stk.empty());
				if (P[i] > stk.back().first) {
					//seg.apply(stk.back().second+1, N, &D::apply, trans_t(true, -1));
					for (int j = stk.back().second+1; j < N; j++) {
						B[j]--;
					}
					stk.pop_back();
				} else {
					break;
				}
			}
			assert(!stk.empty() && P[i] < stk.back().first);
			stk.emplace_back(P[i], i);
			for (int j = i+1; j < N; j++) {
				A[j] += B[j];
			}
		}

		return A;
	};

	auto fwd = solve();
	reverse(P.begin(), P.end());
	auto bwd = solve();
	reverse(P.begin(), P.end());

	if constexpr (TEST) {
		auto fwd_naive = solve_naive();
		reverse(P.begin(), P.end());
		auto bwd_naive = solve_naive();
		reverse(P.begin(), P.end());

		/*
		cerr << "naive answer:\n";
		for (int i = 0; i < N; i++) {
			cerr << fwd_naive[i]+bwd_naive[N-1-i] << " \n"[i+1==N];
		}
		*/
		assert(fwd == fwd_naive);
		assert(bwd == bwd_naive);
	}

	for (int i = 0; i < N; i++) {
		cout << fwd[i] + bwd[N-1-i] << " \n"[i+1==N];
	}

	return 0;
}