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
#include <bits/stdc++.h>
#define maxn 200005
#define inf 1000000000
#define ll long long
using namespace std;

int N;

int wej[maxn];
queue <int> q;
int odl[maxn];

int mini[524288];
int maks[524288];
int todl;
void usun_prz(int p, int k, int wart_poc, int wart_kon, int tp, int tk, int w)// usuwam na przedziale <p, k> gosci <wart_poc, wart_poc>, i daje ich na kolejke i ustawiam im odl = todl
{
	if(wart_kon < mini[w] || maks[w] < wart_poc) return;
	if(tp == tk)
	{
		mini[w] = inf;
		maks[w] = 0;
		q.push(tp);
		odl[tp] = todl;
		return;
	}
	int sr = (tp+tk)>>1;
	if(p <= sr) usun_prz(p, k, wart_poc, wart_kon, tp, sr, w<<1);
	if(sr < k) usun_prz(p, k, wart_poc, wart_kon, sr+1, tk, (w<<1)+1);
	mini[w] = min(mini[w<<1], mini[(w<<1)+1]);
	maks[w] = max(maks[w<<1], maks[(w<<1)+1]);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> wej[i];
	
	for(N = 1; N <= n;) N <<= 1;
	
	fill(mini, mini+(N<<1), inf);
	fill(maks, maks+(N<<1), 0);
	
	for(int i = 1; i <= n; ++i)
	{
		q = queue <int>();
		q.push(i);
		
		fill(odl+1, odl+1+n, inf);
		odl[i] = 0;
		
		for(int j = 1; j <= n; ++j)
		{
			if(j == i) mini[N-1+j] = inf, maks[N-1+j] = 0;
			else mini[N-1+j] = maks[N-1+j] = wej[j];
		}
		for(int j = N; --j;)
		{
			mini[j] = min(mini[j<<1], mini[(j<<1)+1]);
			maks[j] = max(maks[j<<1], maks[(j<<1)+1]);
		}
		
		while(!q.empty())
		{
			int w = q.front();
			q.pop();
			todl = odl[w]+1;
			if(w > 1 && wej[w] < n) usun_prz(1, w-1, wej[w]+1, n, 1, N, 1);
			if(w < n && wej[w] > 1) usun_prz(w+1, n, 1, wej[w]-1, 1, N, 1);
		}
		
		ll wyn = 0ll;
		for(int j = 1; j <= n; ++j) if(odl[j] != inf) wyn += (ll)odl[j];
		cout << wyn << " ";
	}
	
	return 0;
}