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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
#define ll long long 
#define debug if(0)

const int MAX_N = 2e5;
const int base = 1<<18;
const int inf = 1e9;

void insert(int v, int x, std::pair<int, int> t[], bool max) {
    v += base;
    t[v] = {x, v-base};
    v /= 2;
    while (v > 0) {
        if (max) t[v] = std::max(t[v*2], t[v*2+1]);
        else t[v] = std::min(t[v*2], t[v*2+1]);
        v /= 2;
    }
}

std::pair<int, int> query(int L, int R, std::pair<int, int> t[], bool max) {
    if (L > R) {
        if (max) return {-1, 0};
        return {inf, 0};
    }
    L += base; R += base;
    std::pair<int, int> res = std::min(t[L], t[R]);
    if (max) res = std::max(t[L], t[R]);
    while (L/2 != R/2) {
        if (L%2 == 0) {
            if (max) res = std::max(res, t[L+1]);
            else res = std::min(res, t[L+1]);
        } 
        if (R%2 == 1) {
            if (max) res = std::max(res, t[R-1]);
            else res = std::min(res, t[R-1]);
        }
        L /= 2; R /= 2;
    }
    return res;
}

std::pair<int, int> t_max[2*base+5];
std::pair<int, int> t_min[2*base+5];
int a[MAX_N+3];
ll res[MAX_N+3];
int n;

int d[MAX_N+3];
void bfs(int r) {
    for (int i = 1; i <= n; i++) d[i] = -1;

    insert(r, inf, t_min, false);
    insert(r, -1, t_max, true);

    std::queue<int> q; q.push(r);
    d[r] = 0;
    std::pair<int, int> p;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        while (1) {
            p = query(v+1, n, t_min, false);
            if (a[v] > p.first) {
                d[p.second] = d[v]+1;
                q.push(p.second);
                insert(p.second, inf, t_min, false);
                insert(p.second, -1, t_max, true);
            } else break;
        }
        while (1) {
            p = query(1, v-1, t_max, true);
            if (a[v] < p.first) {
                d[p.second] = d[v]+1;
                q.push(p.second);
                insert(p.second, inf, t_min, false);
                insert(p.second, -1, t_max, true);
            } else break;
        }
    }

    debug {
        std::cout << "d[] for root = " << r << "\n";
        for (int i = 1; i <= n; i++) std::cout << d[i] << " ";
        std::cout << "\n";
        fflush(stdout);
    }
}

int main() {
    std::ios_base::sync_with_stdio(0); std::cin.tie(NULL);
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> a[i];

    for (int i = 1; i <= n; i++) {
        insert(i, a[i], t_min, false);
        insert(i, a[i], t_max, true);
    }

    for (int i = 1; i <= n; i++) {
        bfs(i);
        for (int j = 1; j <= n; j++) if (d[j] != -1) {
            res[i] += (ll)(d[j]);
            insert(j, a[j], t_min, false);
            insert(j, a[j], t_max, true);
        }
    }

    for (int i = 1; i <= n; i++) std::cout << res[i] << " ";
    std::cout << "\n";
}