#include<bits/stdc++.h>
#define ll long long
// #define int short
using namespace std;

inline int read(){
	int s=0,k=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-') k=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=(s<<3)+(s<<1)+(c^48);
		c=getchar();
	}
	return s*k;
}

const int inf=0x3f3f,N=5e6+5,M=42;
int f[N],fp[N],num[M],w[M],to[M],val[M],id[M],L[M],a[M],dfn[M],n;
ll g[N],gp[N];

void merge(int &f,ll &g,int fp,ll gp){
	if(fp<f) f=fp,g=gp;
	else if(f==fp) g+=gp;
}

void init(int sig,int &ls,int &lc,int &c,int &s){
	c=0;s=1;
	for(int i=1,j;i<=n;i++){
		if(dfn[i]>sig) continue;
		j=i;
		while(j<=n&&dfn[j]<=sig) j++;
		c++; val[c]=s;
		s*=j-i+1;
		for(int k=i;k<j;k++) to[k]=c;
		i=j-1;
	}
	lc=0;ls=1;
	for(int i=1,j;i<=n;i++){
		if(dfn[i]>=sig) continue;
		j=i;
		while(j<=n&&dfn[j]<sig) j++;
		lc++;
		id[lc]=to[i]; L[lc]=i; w[lc]=j-i+1;
		ls*=w[lc];
		i=j-1;
	}
}

int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		dfn[a[i]]=i;
	}
	f[0]=0;g[0]=1;
	for(int i=1,lc,ls,c,s;i<=n;i++){
		init(i,ls,lc,c,s);
		for(int i=0;i<ls;i++){
			fp[i]=f[i];
			gp[i]=g[i];
		}
		for(int i=0;i<s;i++){
			f[i]=inf;
			g[i]=0;
		}
		for(int j=0;j<ls;j++){
			if(!gp[j]) continue;
			int sum=0,tmp=j,nxt=0;
			for(int k=1;k<=lc;k++){
				num[k]=tmp%w[k];
				tmp/=w[k];
				if(L[k]>a[i]) sum+=num[k];
				nxt+=num[k]*val[id[k]];
			}
			merge(f[nxt],g[nxt],fp[j],gp[j]);
			nxt+=val[to[a[i]]];
			merge(f[nxt],g[nxt],fp[j]+sum,gp[j]);
		}
	}
	for(int i=1;i<=n;i++) printf("%d %lld\n",f[i],g[i]);
	return 0;
}