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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=44;
int n,p[N];

struct Hash_table {
	static const int V=5000019;
	int fst[V],nxt[V];
	int ctm,ptm[V],T;
	int val[V];
	ll key[V],way[V];
	void init() { T=0; ctm++;}
	void upd(ll s,int v,ll w) {
		int S=s%V;
		if (ptm[S]!=ctm) ptm[S]=ctm,fst[S]=-1;
		for (int j=fst[S];j!=-1;j=nxt[j]) if (key[j]==s) {
			if (val[j]>v) val[j]=v,way[j]=0;
			if (val[j]==v) way[j]+=w;
			return;
		}
		nxt[T]=fst[S]; fst[S]=T; key[T]=s; val[T]=v; way[T]=w;
		T++;
	}
}hs[2];
pair<int,ll> ans[N];

int main() {
	scanf("%d",&n);
	rep(i,0,n) scanf("%d",p+i),p[i]--;
	hs[0].init();
	hs[0].upd(0,0,1);
	for (int i=0;i<n;i++) {
		Hash_table &pd=hs[i&1],&dp=hs[1-(i&1)];
		dp.init();
		ll psmall=0,pf1=0,pf2=0,pu=0;
		int mx=n,mn=-1;
		rep(j,i+1,n) {
			if (p[j]>p[i]) mx=min(mx,p[j]);
			if (p[j]<p[i]) mn=max(mn,p[j]);
		}
		rep(j,0,n) {
			if (j>p[i]) psmall|=1ll<<j;
			if (j>mn&&j<p[i]) pf1|=1ll<<j;
			if (j>=p[i]&&j<mx) pf2|=1ll<<j;
			if (j<=mn||j>=mx) pu|=1ll<<j;
		}
		mx--; mn++;
		rep(j,0,pd.T) {
			ll s=pd.key[j];
			ll f1=s&pf1,f2=s&pf2;
			int cs=__builtin_popcountll(f2);
			dp.upd((s&pu)|((((1ll<<cs)-1)*((f1>>mn)+1)<<mn)+f1),pd.val[j],pd.way[j]);
			f2|=1ll<<p[i]; cs++;
			dp.upd((s&pu)|((((1ll<<cs)-1)*((f1>>mn)+1)<<mn)+f1),pd.val[j]+__builtin_popcountll(s&psmall),pd.way[j]);
		}
	}
	Hash_table &pd=hs[n&1];
	rep(j,0,pd.T) {
		ans[__builtin_popcountll(pd.key[j])]=mp(pd.val[j],pd.way[j]);
	}
	rep(i,1,n+1) printf("%d %lld\n",ans[i].fi,ans[i].se);
}