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
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
#include <unordered_map>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 44
int n,a[SZ];
int sf[SZ][SZ],s[SZ],pos[SZ],pl[SZ],pm[SZ],pr[SZ];
#define MOD 10000007
typedef pair<int,ll> pil;
const pil em(0,0);
struct HashTable
{
int h[MOD],nx[9999999],cn=0;
ll rv[9999999]; pil vv[9999999];
pil& operator [] (ll v)
{
	for(int e=h[v%MOD];e;e=nx[e])
		if(rv[e]==v) return vv[e];
	nx[++cn]=h[v%MOD]; rv[cn]=v;
	h[v%MOD]=cn; return vv[cn]=em;
}
void clear()
{
	for(int i=1;i<=cn;++i)
		h[rv[i]%MOD]=0;
	cn=0;
}
}f[2];
inline void Add(pil&a,pil b)
{
	if((!a.se)||a.fi>b.fi) a=b;
	else if(a.fi==b.fi) a.se+=b.se;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",a+i);
	ll tg=0;
	for(int i=1;i<=n;++i)
	{
		for(int j=i;j<=n;++j)
			sf[i][++s[i]]=a[j];
		sf[i][0]=0;
		sf[i][s[i]+1]=n+1;
		sort(sf[i],sf[i]+s[i]+1);
		for(int j=1;j<=s[i];++j)
			if(sf[i][j]==a[i])
				pos[i]=j;
		pl[i]=sf[i][pos[i]-1];
		pm[i]=sf[i][pos[i]];
		pr[i]=sf[i][pos[i]+1];
	}
	f[0][0]=pil(0,1);
	for(int i=1;i<=n;++i)
	{
		HashTable&ls=f[(i-1)&1],&cs=f[i&1];
		cs.clear();
		register int pl_=pl[i],pr_=pr[i],pm_=pm[i];
		for(int t=1;t<=ls.cn;++t)
		{
			register pil gg=ls.vv[t];
			register ll tx=ls.rv[t],ty=0;
			register ll A=(1LL<<(pr_-pl_))-1;
			register int tu=__builtin_popcountll(tx>>pm_),
			ts=__builtin_popcountll((tx>>pl_)&A);
			tx&=(~(A<<pl_));
			ty=tx|(((1LL<<ts)-1)<<pl_);
			tx|=(((1LL<<(ts+1))-1)<<pl_);
			Add(cs[ty],gg);
			gg.fi+=tu;
			Add(cs[tx],gg);
		}
	}
	static pil op[55];
	for(int i=1;i<=f[n&1].cn;++i)
		op[__builtin_popcountll(f[n&1].rv[i])]=f[n&1].vv[i];
//	for(auto u:f[n&1]) op[u.fi]=u.se;
	for(int i=1;i<=n;++i)
		printf("%d %lld\n",op[i].fi,op[i].se);
}