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

int main() {
	int lin;
	std::vector<int> liny;

	std::cin >> lin;
	liny.reserve(lin);

	for (int i=0; i<lin; ++i) {
		int lina;
		std::cin >> lina;
		liny.push_back(lina-1);
	}

	std::vector<std::set<int>> graf;
	graf.resize(lin);

	for (int i=0; i<lin; ++i) {
		for (int j=i+1; j<lin; ++j) {
			if (liny[j] < liny[i]) {
				graf[i].insert(j);
				graf[j].insert(i);
			}
		}
	}

	/*
	for (int i=0; i<lin; ++i) {
		std::cerr << i+1 << ":";
		for (const int &j : graf[i]) {
			std::cerr << j+1 << " ";
		}
		std::cerr << std::endl;
	}
	*/

	for (int i=0; i<lin; ++i) {
		std::set<int> graniczne(graf[i].begin(), graf[i].end());
		std::set<int> wewnętrzne;
		std::set<int> nowe;

		wewnętrzne.insert(i);
		int suma = graniczne.size();
		int odległość = 2;

		while (!graniczne.empty()) {
			for (const int &graniczna: graniczne) {
				for (const int &nowa: graf[graniczna]) {
					if (graniczne.find(nowa) == graniczne.end() && wewnętrzne.find(nowa) == wewnętrzne.end()) {
						nowe.insert(nowa);
						suma += odległość;
					}
				}
			}
			wewnętrzne.merge(graniczne);
			graniczne.clear();
			std::swap(graniczne, nowe);
			++odległość;
		}
		std::cout << suma << " ";
	}
}