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
#include <bits/stdc++.h>


using namespace std;


long long getTotalDist(int v, int n, vector <int> &p, vector <int> &pRev) {
    long long totalDist = 0;

    vector <bool> vis(n, false);
    vis[v] = true;

    int l = v, r = v, lp = p[v], rp = p[v];
    for (int u = 0; u < n; u++) {
        if ((u < v) ^ (p[u] < p[v])) {
            totalDist++;
            vis[u] = true;

            l = min(l, u);
            r = max(r, u);
            lp = min(lp, p[u]);
            rp = max(rp, p[u]);
        }
    }

    int li = v, ri = v, lpi = p[v], rpi = p[v];
    for (int d = 2; d < n; d++) {
        bool any = false;
        int lNew = l, rNew = r, lpNew = lp, rpNew = rp;

        auto process = [&](int u) {
            if (!vis[u]) {
                totalDist += d;
                vis[u] = any = true;

                lNew = min(lNew, u);
                rNew = max(rNew, u);
                lpNew = min(lpNew, p[u]);
                rpNew = max(rpNew, p[u]);
            }
        };

        while (li > l) { process(li--); }
        while (ri < r) { process(ri++); }
        while (lpi > lp) { process(pRev[lpi--]); }
        while (rpi < rp) { process(pRev[rpi++]); }

        if (!any) {
            break;
        }

        l = lNew, r = rNew, lp = lpNew, rp = rpNew;
    }

    return totalDist;
}

vector <long long> solve(int n, vector <int> &p) {
    vector <int> pRev(n);
    for (int i = 0; i < n; i++) {
        pRev[p[i]] = i;
    }

    vector <long long> ans(n, 0);
    for (int v = 0; v < n; v++) {
        ans[v] = getTotalDist(v, n, p, pRev);
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    vector <int> p(n);
    for (int &pi : p) {
        cin >> pi;
        pi--;
    }

    auto ans = solve(n, p);
    for (long long x : ans) {
        cout << x << ' ';
    }

    return 0;
}