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
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
int n,dokad[200001],skad[200001];
int najdnalp[200001][4];
int najw,najm=INT_MAX;
int doj[200001][2];
vector<int>pol[501];
void st1()
{
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&dokad[i]);
		skad[dokad[i]]=i;
		for(int j=1;j<n;++j)
			if(dokad[j]>dokad[i])
				pol[i].push_back(j);
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<dokad[i];++j)
			if(skad[j]>i)
				pol[i].push_back(skad[j]);

	queue<int>kol;
	int a;
	for(int i=1;i<=n;++i)
	{
		long long odp=0;
		doj[i][0]=0;
		doj[i][1]=i;
		kol.push(i);
		while(!kol.empty())
		{
			a=kol.front();
			kol.pop();
			odp+=doj[a][0];
			for(auto j:pol[a])
				if(doj[j][1]!=i)
				{
					doj[j][1]=i;
					doj[j][0]=doj[a][0]+1;
					kol.push(j);
				}
		}
		printf("%lld ",odp);
	}
}
int main()
{
	scanf("%d",&n);
	if(n<=500)
	{
		st1();
		return 0;
	}
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&dokad[i]);
		skad[dokad[i]]=i;
		najw=max(najw,dokad[i]);
		najdnalp[i][0]=skad[najw];
	}
	for(int i=n;i;--i)
	{
		najm=min(najm,skad[i]);
		najdnalp[skad[i]][1]=najm;
	}
	najw=0;
	for(int i=1;i<=n;++i)
	{
		najw=max(najw,skad[i]);
		najdnalp[skad[i]][2]=najw;
	}
	najm=INT_MAX;
	for(int i=n;i;--i)
	{
		najm=min(najm,dokad[i]);
		najdnalp[i][3]=skad[najm];
	}
	queue<int>kol;
	int a;
	// cout<<najdnalp[4][0]<<" "<<najdnalp[4][1]<<" "<<najdnalp[4][2]<<" "<<najdnalp[4][3]<<endl;
	// return 0;
	for(int i=1;i<=n;++i)
	{
		long long odp=0;
		doj[i][0]=0;
		doj[i][1]=i;
		kol.push(i);
		while(!kol.empty())
		{
			a=kol.front();
			kol.pop();
			for(int j=0;j<4;++j)
				if(doj[najdnalp[a][j]][1]!=i)
				{
					doj[najdnalp[a][j]][1]=i;
					doj[najdnalp[a][j]][0]=doj[a][0]+1;
					kol.push(najdnalp[a][j]);
				}
		}
		for(int j=1;j<=n;++j)
		{
			if(doj[j][1]==i)
				odp+=doj[j][0];
			else
			{
				int malo=INT_MAX;
				for(int k=0;k<4;++k)
				{
					if(doj[najdnalp[j][k]][1]==i)
						malo=min(malo,doj[najdnalp[j][k]][0]+1);
				}
				if(malo!=INT_MAX)
					odp+=malo;
					// if(i==4)
					// 	cout<<"aaa"<<j<<" "<<malo<<"aaa"<<endl;
			}
		}
		printf("%lld ",odp);
	}
	return 0;
}