#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int long long
const int N = 300005;

int a[N],st[N],tp,n;
int pre[N],suf[N];
vector<int> G[N];
int siz[N],sum[N],ans[N],res[N],presum[N];
void dfs(int u)
{
	siz[u]=1;
	for(int v:G[u])
	{
		dfs(v),siz[u]+=siz[v];
		sum[u]+=sum[v]+siz[v];
	}
}
signed main() {
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	st[0]=0;
	for(int i=1;i<=n;i++)
	{
		pre[i]=st[tp];
		while(tp&&a[i]>a[st[tp]]) tp--;
		st[++tp]=i;
	}
	st[0]=n+1; tp=0;
	for(int i=n;i>=1;i--)
	{
		suf[i]=st[tp];
		while(tp&&a[i]>a[st[tp]]) tp--;
		st[++tp]=i;
	}
	int rt=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==n)
		{
			rt=i;
			continue;
		}
		int to=a[pre[i]]>a[suf[i]]?pre[i]:suf[i];
		G[to].push_back(i);
		printf("%d %d\n",to,i);
	}
	dfs(rt);
	for(int i=1;i<=n;i++) printf("%d %d\n",siz[i],sum[i]);
	for(int i=1;i<=n;i++)
	{
		if(a[i]==n) res[i]=sum[i];
		else res[i]=-siz[i];
	}
	for(int i=1;i<=n;i++) presum[i]=presum[i-1]+res[i];
	int cur=0;
	st[0]=0; tp=0;
	for(int i=1;i<=n;i++)
	{
		while(tp&&a[i]>a[st[tp]]) cur-=res[st[tp]],tp--;
		ans[i]-=presum[st[tp]];
		ans[i]+=cur;
		st[++tp]=i,cur+=res[i];
	}
	st[0]=n+1; tp=0; cur=0;
	for(int i=n;i>=1;i--)
	{
		while(tp&&a[i]>a[st[tp]]) cur-=res[st[tp]],tp--;
		ans[i]+=presum[st[tp]-1];
		ans[i]+=cur;
		st[++tp]=i,cur+=res[i];
	}
	for(int i=1;i<=n;i++) ans[i]+=n-1;
	for(int i=1;i<=n;i++) printf("%lld%c",ans[i]," \n"[i==n]);
	return 0;
}
/*
2 1
2 3
5 4
6 5
5 6
1 0
3 2
1 0
0 0
0 0
0 0
6 5 6 6 6 7

*/