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
//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 200 * 1000 + 10;
int n;
int p[nax];
vi V[nax];
int mx[nax], mi[nax];
const int INF = 1e9;
int dist[nax][5];
bool vis[nax];

void bfs(int x, int id) {
	for (int i = 1; i <= n; ++i) {
		dist[i][id] = INF;
		vis[i] = false;
	}
	dist[x][id] = 0;
	queue<int>Q;
	Q.push(x);
	vis[x] = true;
	while (!Q.empty()) {
		x = Q.front();
		Q.pop();
		for (auto nbh : V[x]) if (!vis[nbh]) {
			dist[nbh][id] = dist[x][id] + 1;
			vis[nbh] = 1;
			Q.push(nbh);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> p[i];
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			if (p[j] < p[i]) {
				V[j].PB(i);
				V[i].PB(j);
			}
		}
	}
	mx[1] = 1;
	for (int i = 2; i <= n; ++i) {
		mx[i] = mx[i - 1];
		if (p[i] > p[mx[i]]) {
			mx[i] = i;
		}
	}
	mi[n] = n;
	for (int i = n - 1; i >= 1; --i) {
		mi[i] = mi[i + 1];
		if (p[i] < p[mi[i]]) {
			mi[i] = i;
		}
	}
	for (int i = 1; i <= n; ++i) {
		bfs(i, 0);
		bfs(mi[i], 1);
		bfs(mx[i], 2);
		ll ans = 0;
		for (int j = 1; j <= n; ++j) {
			int me = min({dist[j][0], dist[j][1] + 1, dist[j][2] + 1});
			if (me <= n) {
				ans += me;
			}
		}
		cout << ans << " ";
	}
}