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
#include <stdio.h>
#include <algorithm>
using namespace std;
const int C=5001, Inf=1000000001; //Zmienić przy maxowaniu

int seq[C], inverse_seq[C];
int proper_max[2][C], dp[2][C][C];
int main(){
	int i, n;
	scanf ("%d", &n);

	for (int i=1; i<=n; i++){
	       	scanf ("%d", &seq[i]);
		inverse_seq[seq[i]] = i;
	}

	for (int i=1; i<=n; i++){
		proper_max[0][i] = max(proper_max[0][i-1], seq[i]);
		proper_max[1][i] = max(proper_max[1][i-1], inverse_seq[i]);
	}

	for (int i=0; i<=n; i++){
		for (int j=0; j<=n; j++) dp[0][i][j] = Inf;
		for (int j=0; j<=n; j++) dp[1][i][j] = Inf;
		dp[0][i][seq[i]] = 0;
		dp[1][i][inverse_seq[i]] = 0;
	}

	for (int x=n; x>=1; x--){
		int lower_border = proper_max[1][seq[x]-1]; //kres na dnie
		int upper_border = proper_max[0][x-1]; //start z dołu, kres w górze
		
		if (lower_border < x) lower_border = 0;
		if (upper_border < seq[x]) upper_border = 0;

		for (int j = seq[x]+1; j<=n ; j++){
			if (inverse_seq[j] <= x) dp[0][x][j] = 1;
			else dp[0][x][j] = min(dp[0][lower_border][j], dp[1][upper_border][inverse_seq[j]])+1;
		}

		lower_border = proper_max[1][x-1]; //kres na dnie
		upper_border = proper_max[0][inverse_seq[x]-1]; //start z dołu, kres w górze

		if (lower_border < inverse_seq[x]) lower_border = 0;
		if (upper_border < x) upper_border = 0;

		for (int j = inverse_seq[x]+1; j<=n ; j++){
			if (seq[j] <= x) dp[1][x][j] = 1;
			else dp[1][x][j] = min(dp[0][lower_border][seq[j]], dp[1][upper_border][j])+1;
		}
	}

	for (int i=1; i<=n; i++){
		int res=0, post;
		for (int j=1; j<seq[i]; j++){
		       	post = dp[0][inverse_seq[j]][seq[i]];
			if (post < Inf) res += post;
		}
		for (int j=seq[i]; j<=n; j++){
		       	post = dp[0][i][j];
			if (post < Inf) res += post;
		}
		printf ("%d ", res);
	}
	printf ("\n");

return 0;}