1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 2e5 + 10, S = 4e6;
int n, p[N], q[N], fa[N], id[N], rt[N];
int type;
i64 ans1[N], ans2[N];
unordered_map<i64, i64> mp;
vector<int> pre, suf;
struct ChairmanTree {
	int cnt, sum[S], ls[S], rs[S];
	int copy(int v) {
		int u = ++ cnt; sum[u] = sum[v], ls[u] = ls[v], rs[u] = rs[v];
		return u;
	}
	void ins(int &u, int l, int r, int p) {
		sum[u = copy(u)] ++;
		if(l == r) return ;
		int mid = l + r >> 1;
		p <= mid ? ins(ls[u], l, mid, p) : ins(rs[u], mid + 1, r, p);
	}
	int query(int u, int l, int r, int ql, int qr) {
		if(!u) return 0;
		if(l >= ql && r <= qr) return sum[u];
		int mid = l + r >> 1;
		if(qr <= mid) return query(ls[u], l, mid, ql, qr);
		else if(ql > mid) return query(rs[u], mid + 1, r, ql, qr);
		else return query(ls[u], l, mid, ql, qr) + query(rs[u], mid + 1, r, ql, qr);
	}
	void clear() {cnt = 0;}
}ds;
void work(int n) {
	ds.clear();
	for(int i = 1; i <= n; i ++) ds.ins(rt[i] = rt[i - 1], 1, n, q[i]);
	function<i64(int, int, int, int)> get = [&] (int x, int y, int qx, int qy) {
		if(mp.count(1ll * qx * N + qy)) return mp[1ll * qx * N + qy];
		i64 &ans = mp[1ll * qx * N + qy];
		ans = type == 0 ? n - qy + 1 - ds.query(rt[qx - 1], 1, n, qy, n) : ds.query(rt[n - qx + 1], 1, n, 1, n - qy + 1);
		if(x != pre.back() && y != suf.back()) ans += get(fa[y], fa[x], y + 1, q[x] + 1);
		return ans;
	};
	auto solve = [&] (i64 *ans) {
		for(int i = 1, mx = 0; i <= n; i ++) {
			if(q[i] > mx) {
				mx = q[i];
				pre.emplace_back(i);
			}
		}
		for(int i = n, mn = n + 1; i >= 1; i --) {
			if(q[i] < mn) {
				mn = q[i];
				suf.emplace_back(i);
			}
		}
		reverse(suf.begin(), suf.end());
		for(int i = 0, j = 0; i < pre.size(); i ++) {
			while(j + 1 < suf.size() && q[suf[j + 1]] < q[pre[i]]) j ++;
			fa[pre[i]] = suf[j]; id[pre[i]] = i;
		}
		for(int i = 0, j = 0; i < suf.size(); i ++) {
			while(j + 1 < pre.size() && pre[j + 1] < suf[i]) j ++;
			fa[suf[i]] = pre[j]; id[suf[i]] = i;
		}
		for(int i = 1; i <= n; i ++) {
			int u = upper_bound(pre.begin(), pre.end(), i) - pre.begin() - 1;
			int v = upper_bound(suf.begin(), suf.end(), i, [&] (int x, int y) {return q[x] < q[y];}) - suf.begin() - 1;
			ans[i] = get(pre[u], suf[v], i + 1, q[i] + 1);
		}
	};
	mp.clear(), pre.clear(), suf.clear(); type = 0;
	for(int i = 1; i <= n; i ++) id[i] = fa[i] = 0;
	solve(ans1);
	reverse(q + 1, q + n + 1);
	for(int i = 1; i <= n; i ++) q[i] = n - q[i] + 1;
	mp.clear(), pre.clear(), suf.clear(); type = 1;
	for(int i = 1; i <= n; i ++) id[i] = fa[i] = 0;
	solve(ans2);
	for(int i = 1; i <= n; i ++) cout << ans1[i] + ans2[n - i + 1] + n - 1 << ' ';
}
int main() {
	// freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> p[i];
	int last = 1;
	for(int i = 1, mx = 0; i <= n; i ++) {
		mx = max(mx, p[i]);
		if(mx == i) {
			int m = i - last + 1;
			for(int j = 1; j <= m; j ++) q[j] = p[j + last - 1] - last + 1;
			work(m);
			last = i + 1;
		}
	}
	return 0;
}