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
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;

int tab[200009], invtab[200009], col[200009];

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, a, b, c, inva, invb, olda, oldb, oldinva, oldinvb, newa, newb, newinva, newinvb;
	long long wyn, x;
	cin>>n;
	for(int i=1; i<=n; i++) cin>>tab[i];
	for(int i=1; i<=n; i++) invtab[tab[i]] = i;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++) col[j] = 0;
		col[i] = 1;
		wyn = 0;
		x = 1;
		a = b = newa = newb = i;
		inva = invb = newinva = newinvb = tab[i];
		for(int j=1; j<=n; j++)
		{
			if(j == i) continue;
			if((i < j && tab[i] > tab[j]) || (i > j && tab[i] < tab[j]))
			{
				newa = min(newa, j);
				newb = max(newb, j);
				newinva = min(newinva, tab[j]);
				newinvb = max(newinvb, tab[j]);
				wyn++;
				col[j] = 1;
			}
		}
		while(a != newa || b != newb || inva != newinva || invb != newinvb)
		{
			olda = a; oldb = b; oldinva = inva; oldinvb = invb;
			a = newa; b = newb; inva = newinva; invb = newinvb;
			x++;
			for(int j=olda-1; j>=a; j--)
			{
				if(col[j] == 0)
				{
					newinva = min(newinva, tab[j]);
					newinvb = max(newinvb, tab[j]);
					wyn += x;
					col[j] = 1;
				}
			}
			for(int j=oldb+1; j<=b; j++)
			{
				if(col[j] == 0)
				{
					newinva = min(newinva, tab[j]);
					newinvb = max(newinvb, tab[j]);
					wyn += x;
					col[j] = 1;
				}
			}
			for(int j=oldinva-1; j>=inva; j--)
			{
				c = invtab[j];
				if(col[c] == 0)
				{
					newa = min(newa, c);
					newb = max(newb, c);
					wyn += x;
					col[c] = 1;
				}
			}		
			for(int j=oldinvb+1; j<=invb; j++)
			{
				c = invtab[j];
				if(col[c] == 0)
				{
					newa = min(newa, c);
					newb = max(newb, c);
					wyn += x;
					col[c] = 1;
				}
			}
		}
		cout<<wyn<<" ";
	}
	return 0;
}