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

using namespace std;

struct FindUnion {
	int n = 0;
	int componentsNum;
	vector<int> sizes, P;

	FindUnion(int n) {
		this->n = n;
		componentsNum = n;
		sizes.resize(n, 1);
		P.resize(n);
		for (int i = 0; i < n; i++) P[i] = i;
	}

	int find(int v) {
		int root = v;
		while (root != P[root]) root = P[root];
		while (v != root) {
			int next = P[v];
			P[v] = root;
			v = next;
		}
		return root;
	}

	void unify(int v, int u) {
		int root1 = find(v), root2 = find(u);
		if (root1 == root2) return;
		if (sizes[root1] >= sizes[root2]) {
			sizes[root1] += sizes[root2];
			P[root2] = root1;
		}
		else {
			sizes[root2] += sizes[root1];
			P[root1] = root2;
		}
		componentsNum--;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, k;
	cin >> n >> k;

	int nn = 2 * n;

	vector<int> V(nn);
	for (auto& v : V)
		cin >> v;

	vector<int> M(nn + 1);
	for (int i = 0; i < nn; i++)
		M[V[i]] = i;

	vector<int> R(k);

	for (int l = 1; l <= nn; l++) {
		FindUnion fu(nn);
		int res = 0;
		for (int r = l; r <= nn; r++) {
			int m = M[r];
			int isr = n * (m >= n);
			int a = (m - 1 + n) % n + isr;
			int b = (m + 1) % n + isr;
			int c = (m + n) % nn;

			int cn = fu.componentsNum;

			if (V[a] >= l && V[a] <= r)
				fu.unify(m, a);
			if (V[b] >= l && V[b] <= r)
				fu.unify(m, b);
			if (V[c] >= l && V[c] <= r)
				fu.unify(m, c);

			int ri = (r - l) - (nn - fu.componentsNum);
			if (ri < k)
				R[ri]++;
		}
	}

	for (auto& r : R)
		cout << r << ' ';
}