人已经急了。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define cpy(x, y, s) memcpy(x, y, sizeof(x[0]) * (s))
#define mem(x, k) memset(x, k, sizeof(x))
#define ll long long
#define lc x << 1
#define rc x << 1 | 1
#define se(x) tr[x].info.se
#define v(x) tr[x].info.v
#define oc(x) tr[x].info.oc
#define voc(x) tr[x].info.voc
#define sum(x) tr[x].info.sum

// \yhx-12243/ 鱼大保佑！！

using namespace std;

const int _ = 2e5 + 5;

struct Info {
	int v, se, oc, voc, soc;
	ll sum;
	void add (int x, int y) {
		v += x, se += y;
		sum += 1ll * voc * x + 1ll * soc * y;
	}
	void clear () { v = se = oc = voc = soc = sum = 0; }
};
Info operator + (Info x, Info y) {
	Info u;
	u.v = max(x.v, y.v), u.sum = x.sum + y.sum, u.oc = x.oc + y.oc;
	u.voc = x.voc + y.voc;
	if (x.v > y.v) {
		u.se = max(x.se, y.v), u.voc = x.voc, u.soc = x.soc + y.voc + y.soc; 
	}
	else if (x.v < y.v) {
		u.se = max(x.v, y.se), u.voc = y.voc, u.soc = y.soc + x.voc + x.soc; 
	}
	else if (x.v == y.v) {
		u.se = max(x.se, y.se), u.voc = x.voc + y.voc, u.soc = x.soc + y.soc; 
	}
	return u;
}
struct node {
	Info info;
	int vtag, stag;
	void apply (int a, int b, int f) {
		if (f) info.add(a, b), vtag += a, stag += b;
		else info.add(b, b), vtag += b, stag += b;
	}
} tr[_ << 2];
void pushup (int x) { tr[x].info = tr[lc].info + tr[rc].info; }
void pushdown (int x) {
	tr[lc].apply(tr[x].vtag, tr[x].stag, (v(lc) >= v(rc)));
	tr[rc].apply(tr[x].vtag, tr[x].stag, (v(rc) >= v(lc)));
	tr[x].vtag = tr[x].stag = 0;
}
int modify (int x, int l, int r, int ql, int qr) {
	if (ql > r || qr < l) return 0;
	if (ql <= l && qr >= r) return tr[x].apply(1, 1, 1), oc(x);
	int mid = (l + r) >> 1, ret = 0; pushdown(x);
	ret = modify(lc, l, mid, ql, qr) + modify(rc, mid + 1, r, ql, qr), pushup(x);
	return ret;
}
void add (int x, int l, int r, int p, int k) {
	if (l == r) {
		sum(x) = v(x) = k, voc(x) = oc(x) = 1;
		return ;
	}
	int mid = (l + r) >> 1; pushdown(x);
	if (p <= mid) add(lc, l, mid, p, k);
	else add(rc, mid + 1, r, p, k);
	pushup(x);
}
void RangeMin (int x, int l, int r, int ql, int qr, int k) {
	if (ql > r || qr < l || k >= v(x)) return ;
	if (ql <= l && r <= qr && k > se(x)) {
		return tr[x].apply(min(k - v(x), 0), 0, 1);	
	}
	int mid = (l + r) >> 1; pushdown(x);
	RangeMin(lc, l, mid, ql, qr, k), RangeMin(rc, mid + 1, r, ql, qr, k);
	pushup(x);
}
void clear (int x, int l, int r) {
	tr[x].vtag = tr[x].stag = 0, tr[x].info.clear();
	if (l == r) return ;
	int mid = (l + r) >> 1;
	clear(lc, l, mid), clear(rc, mid + 1, r);
}

int n, p[_];
ll res[_];
int main () {
	freopen("darkyangli.in", "r", stdin);
//	freopen("darkyangli.out", "w", stdout);
	cin >> n;
	rep(i, 1, n) { int x; scanf("%d", & x); p[x] = i; }
	rep(t, 1, 2) {
		clear(1, 1, n);
		for (int i = 1, x; i <= n; ++ i) {
			x = modify(1, 1, n, p[i] + 1, n);
			add(1, 1, n, p[i], i + 1);
			RangeMin(1, 1, n, 1, p[i] - 1, i - x);
			res[i] += sum(1);
			//cout << sum(1) << endl;
		}
		rep(i, 1, n) p[i] = n - p[i] + 1;
	}
	rep(i, 1, n) printf("%lld\n", res[i] - 1ll * i * (i + 2));
	return 0;
}