#include<bits/stdc++.h>
#define N 45
#define NN 5000000
#define ll long long
using namespace std;
const int INF=1e9;
int n,a[N],p[N],bl[N][N],len[N][N],val[N][N],d[N],pc[N][NN];
struct node{
	int mn;
	ll val;
	inline void add(node b){
		if(mn==b.mn) val+=b.val;
		if(b.mn<mn) mn=b.mn,val=b.val;
		return;
	}
}f[NN],g[NN],ans[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) p[a[i]]=i;
	for(int i=0;i<=n;i++){
		int p=0,tot=0;
		for(int j=1;j<=n;j++){
			if(a[j]>i){
				bl[i][j]=p;
				continue;
			}
			if(j==1||a[j-1]>i){
				if(p) len[i][p]=tot;
				p++;
				tot=0;
			}
			bl[i][j]=p;
			tot++;
		}
		if(p) len[i][p]=tot;
		d[i]=p;
		val[i][0]=1;
		for(int j=1;j<=p;j++) val[i][j]=val[i][j-1]*(len[i][j]+1);
		for(int j=0,k=0;j<val[i][p];j++){
			if(j>=val[i][k]) k++;
			if(!k) pc[i][j]=0;
			else pc[i][j]=pc[i][j%val[i][k-1]]+j/val[i][k-1];
		}
	}
	f[0]=(node){0,1};
	for(int i=1;i<=n;i++){
		for(int j=0;j<val[i][d[i]];j++) g[j]=(node){INF,0};
		for(int j=0;j<val[i-1][d[i-1]];j++){
			int v=0,num=1;
			if(p[i]-1>=1&&a[p[i]-1]<=i-1){
				v+=j%val[i-1][bl[i-1][p[i]-1]-1];
				num+=(j/val[i-1][bl[i-1][p[i]-1]-1])%(len[i-1][bl[i-1][p[i]-1]]+1);
			}else v+=j%val[i-1][bl[i-1][p[i]]];
			if(p[i]+1<=n&&a[p[i]+1]<=i-1){
				v+=j/val[i-1][bl[i-1][p[i]+1]]*val[i][bl[i][p[i]+1]];
				num+=(j/val[i-1][bl[i-1][p[i]]])%(len[i-1][bl[i-1][p[i]+1]]+1);
			}else v+=j/val[i-1][bl[i-1][p[i]]]*val[i][bl[i][p[i]]];
			v+=num*val[i][bl[i][p[i]]-1];
			g[v].add((node){f[j].mn+pc[i-1][j-j%val[i-1][bl[i-1][p[i]]]],f[j].val});
			v-=val[i][bl[i][p[i]]-1];
			g[v].add(f[j]);
		}
		for(int j=0;j<val[i][d[i]];j++) f[j]=g[j];
	}
	for(int i=1;i<=n;i++) ans[i]=(node){INF,0};
	for(int i=0;i<val[n][d[n]];i++) ans[pc[n][i]].add(f[i]);
	for(int i=1;i<=n;i++) printf("%d %lld\n",ans[i].mn,ans[i].val);
}