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
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define PPC(x) __builtin_popcount((x))
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define st first
#define nd second
#define ithBit(m, i) ((m) >> (i) & 1)
using namespace std;

const int maxN = 41;
int n, P[maxN];
pair <int, int> res[maxN];

int biggerOn(int m, int i)
{
	i = (1 << i) - 1;
	i = ~i;
	return PPC(m & i);
}

int noInvs(int m)
{
	int vals = 0, res = 0;
	FOR(i, 0, n) if (ithBit(m, i))
	{
		int v = P[i]-1;
		res += biggerOn(vals, v);
		vals |= 1 << v;
	}
	return res;
}

void print(int m)
{
	FOR(i, 0, n)
		if (ithBit(m, i))
			printf("%d ", P[i]);
	printf("\n");
}

int main()
{
	scanf ("%d", &n);
	FOR(i, 0, n)
		scanf ("%d", P+i), res[i+1].st = n * n;
		
	FOR(m, 1, 1<<n)
	{
		 int k = PPC(m), invs = noInvs(m);
		 if (invs < res[k].st)
		 	res[k] = {invs, 0};
		 if (invs == res[k].st)
		 	res[k].nd++;
	}
		
	FOR(k, 1, n+1)
		printf("%d %d\n", res[k].st, res[k].nd);
	return 0;
}