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
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
using namespace std;

const int N = 200000 + 9;
int n;
int p[N];

int main() {
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) scanf("%d", p + i);

	for (int x=1; x<=n; ++x) {
		int res = 0;
		vector<int> dist(n + 1, -1);
		queue<int> q;
		q.push(x);
		dist[x] = 0;
		while (!q.empty()) {
			int a = q.front(); q.pop();
			res += dist[a];
			for (int b=1; b<=n; ++b) {
				if (dist[b] >= 0) continue;
				if (a < b && p[a] < p[b]) continue;
				if (a > b && p[a] > p[b]) continue;
				dist[b] = dist[a] + 1;
				q.push(b);
			}
		}
		printf("%d%s", res, x<n ? " " : "\n");
	}

	return 0;
}