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
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef int lld;
typedef unsigned long long llu;
typedef double lf;
typedef long double llf;
typedef pair<int,int> pii;
#define pb push_back
#define mpii make_pair
#define dd second
#define ff first
#define sz size()
#define For(i,s,a) for(lld i=(lld)s;i<(lld)a;++i)

int c[41];
int mp[41];
int dp[32][512];

int32_t main(void){
	int a;
	scanf("%d", &a);
	//a = 24;
	For(i,0,a)scanf("%d", &c[i]);
	//c[i] = i+1;
	For(i,0,a-1)
	For(j,i+1,a)if(c[j] < c[i])mp[j] |= (1<<i);
	int up = 1<<a;
	For(x,1,up){
		lld tmp = 0;
		lld X = x;
		while(X) {
			lld i = __builtin_ctz(X);
			//cout<<X<<" "<<i<<endl;
			tmp += __builtin_popcount(mp[i] & x);
			X -= 1ll<<i;
		}
		lld _ = __builtin_popcount(x);
		++dp[_][tmp];
	}
	For(i,1,a+1){
		int tmp = 0;
		while(!dp[i][tmp])++tmp;
		printf("%d %d\n",tmp,dp[i][tmp]);
	}
}