#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=42,M=3.2e6;
int n,a[N],vis[N];
int b[N],m1,c[N],m2;
int p[N],q[N];
struct node{
	int x;ll y;
	node(int xx=N*N,int yy=0){x=xx,y=yy;}
}f[M],g[M];
const node empty;
int sz[M];
node operator +(node a,int b){
	return (node){a.x+b,a.y};
}
node operator +(node a,node b){
	if(a.x<b.x)return a;
	if(a.x>b.x)return b;
	return (node){a.x,a.y+b.y};
}
node operator +=(node &a,node b){
	return a=a+b;
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	f[0]=(node){0,1};
	p[0]=1;
	for(int i=1;i<=n;i++){
//		printf("Work:%d\n",i);
		int x=0;
		if(vis[a[i]-1]&&vis[a[i]+1]){
			m2=m1-1;
			x=vis[a[i]-1];
			for(int j=1;j<x;j++)c[j]=b[j];
			c[x]=b[x]+b[x+1]+1;
			for(int j=x+1;j<=m2;j++)c[j]=b[j+1];
			q[0]=1;
			for(int j=1;j<=m2;j++)q[j]=q[j-1]*(c[j]+1);
			for(int j=1;j<=m1;j++){
				for(int s=0;s<p[j-1];s++)for(int k=1;k<=b[j];k++){
					sz[s+k*p[j-1]]=sz[s]+(j>x?k:0);
				}
			}
//			printf("Now:%d\n",x);
//			for(int j=1;j<=m1;j++)printf("%d ",p[j]);puts("");
//			for(int j=1;j<=m2;j++)printf("%d ",q[j]);puts("");
			for(int s=0;s<p[m1];s++){
				int t=s%p[x-1]+s/p[x+1]*q[x]+(s/p[x-1]%(b[x]+1)+s/p[x]%(b[x+1]+1))*q[x-1];
				g[t]+=f[s],g[t+q[x-1]]+=(f[s]+sz[s]);
//				printf("%d %d\n",s,t);
			}
			vis[a[i]]=x;
			for(int j=a[i]+1;j<=n;j++)if(vis[j])--vis[j];
		}else if(vis[a[i]-1]||vis[a[i]+1]){
			x=vis[a[i]-1]+vis[a[i]+1];
			int y=vis[a[i]-1]?x:x-1;
			m2=m1;
			for(int j=1;j<=m2;j++)c[j]=b[j];
			p[0]=1,q[0]=1;
			for(int j=1;j<=m1;j++)p[j]=p[j-1]*(b[j]+1);
			for(int j=1;j<=m2;j++)q[j]=q[j-1]*(c[j]+1);
			for(int j=1;j<=m1;j++){
				for(int s=0;s<p[j-1];s++)for(int k=1;k<=b[j];k++){
					sz[s+k*p[j-1]]=sz[s]+(j>y?k:0);
				}
			}
			for(int s=0;s<p[m1];s++){
				int t=s%p[x]+s/p[x]*q[x];
				g[t]=f[s],g[t+q[x-1]]+=(f[s]+sz[s]);
			}
			vis[a[i]]=x;
		}else{
			m2=m1+1;
			int l=a[i];
			while(l&&!vis[l])--l;
			int x=vis[l]+1;
			for(int j=1;j<x;j++)c[j]=b[j];
			c[x]=1;
			for(int j=x+1;j<=m2;j++)c[j]=b[j-1];
			q[0]=1;
			for(int j=1;j<=m2;j++)q[j]=q[j-1]*(c[j]+1);
			for(int j=1;j<=m1;j++){
				for(int s=0;s<p[j-1];s++)for(int k=1;k<=b[j];k++){
					sz[s+k*p[j-1]]=sz[s]+(j>=x?k:0);
				}
			}
			for(int s=0;s<p[m1];s++){
				int t=s%p[x-1]+s/p[x-1]*q[x];
				g[t]=f[s],g[t+q[x-1]]+=(f[s]+sz[s]);
			}
			vis[a[i]]=x;
			for(int j=a[i]+1;j<=n;j++)if(vis[j])++vis[j];
		}
		m1=m2;
		for(int j=1;j<=m1;j++)b[j]=c[j];
		for(int j=0;j<=m1;j++)p[j]=q[j];
		for(int s=0;s<p[m1];s++)f[s]=g[s],g[s]=empty;
//		for(int j=1;j<=m1;j++)printf("%d ",b[j]);puts("");
//		for(int j=1;j<=n;j++)printf("%d ",vis[j]);puts("");
//		for(int s=0;s<p[m1];s++)printf("Node:%d %d %d\n",s,f[s].x,f[s].y);
	}
	for(int i=1;i<=n;i++)printf("%d %lld\n",f[i].x,f[i].y);
}