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
#include <iostream>
#include <vector>
#include <queue>

namespace {
    using std::cin;
    using std::cout;
    using crosses_t = std::vector<size_t>;
    using lines_t = std::vector<crosses_t>;
    using ends_t = crosses_t;
    using counters_t = crosses_t;
    using queue_t = std::queue<size_t>;

    void count_bfs(lines_t const & lines, size_t line, counters_t & counters) {
        queue_t q;
        size_t u;
        q.push(line);
        while (!q.empty()) {
            u = q.front();
            for (size_t l = 0; l < lines[u].size(); ++l) {
                if (counters[lines[u][l]] == 0 && lines[u][l] != line) {
                    counters[lines[u][l]] = counters[u] + 1;
                    q.push(lines[u][l]);
                }
            }
            q.pop();
        }
    }
}

int main() {
    size_t n;
    cin >> n;
    lines_t lines(n);
    ends_t ends(n);
    for (size_t i = 0; i < n; ++i) {
        cin >> ends[i];
    }
    for (size_t i = 0; i < n - 1; ++i) {
        for (size_t j = i + 1; j < n; ++j) {
            if (ends[i] > ends[j]) {
                lines[i].push_back(j);
                lines[j].push_back(i);
            }
        }
    }
    size_t line_result = 0;
    for (size_t i = 0; i < n; ++i) {
        line_result = 0;
        if (lines[i].size() > 0) {
            counters_t d(n, 0);
            count_bfs(lines, i, d);
            for (auto const & x : d)
                line_result += x;
        }
        cout << line_result << ' ';
    }
    cout << '\n';
    return 0;
}