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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n, pol_n, dl, reszta, gdzie, result;
int tab[45];
int res[45];
long long ile[45];
int potegi[30];
int F[1100000];
int F_dl[1100000];
vector <int> jedynki[1100000];
vector <int>::iterator it;
int S[1100000];
int S_dl[1100000];
int jedynka[1100000];
int T[25][1100000];

int main ()
{
	potegi[0] = 1;
	for (int i = 1; i < 30; ++i) potegi[i] = 2 * potegi[i - 1];
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) res[i] = 1000000000;
	pol_n = n / 2;
	reszta = n - pol_n;
	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &tab[i]);
		tab[i]--;
	}
	if (n == 1)
	{
		printf("0 1\n");
		return 0;
	}
	for (int i = 1; i < potegi[pol_n]; ++i)
	{
		gdzie = 0;
		while (!(i & potegi[gdzie])) gdzie++;
		F[i] = F[i ^ potegi[gdzie]];
		jedynki[i].push_back(gdzie);
		F_dl[i] = 1;
		for (int j = gdzie + 1; j < pol_n; ++j) if (i & potegi[j])
		{
			jedynki[i].push_back(j);
			F_dl[i]++;
			if (tab[gdzie] > tab[j]) F[i]++;
		}
	}
	for (int i = 1; i < potegi[reszta]; ++i)
	{
		gdzie = 0;
		while (!(i & potegi[gdzie])) gdzie++;
		S[i] = S[i ^ potegi[gdzie]];
		jedynka[i] = gdzie;
		S_dl[i] = 1;
		for (int j = gdzie + 1; j < reszta; ++j) if (i & potegi[j])
		{
			S_dl[i]++;
			if (tab[gdzie + pol_n] > tab[j + pol_n]) S[i]++;
	    }
	}
	for (int i = 0; i < pol_n; ++i) for (int j = 1; j < potegi[reszta]; ++j)
	{
		T[i][j] = T[i][j ^ potegi[jedynka[j]]];
		if (tab[i] > tab[jedynka[j] + pol_n]) T[i][j]++;
	}
	for (int i = 0; i < potegi[pol_n]; ++i) for (int j = 0; j < potegi[reszta]; ++j)
	{
		result = F[i] + S[j];
		dl = F_dl[i] + S_dl[j];
		for (it = jedynki[i].begin(); it != jedynki[i].end(); ++it) result += T[*it][j];
		if (result < res[dl])
		{
			res[dl] = result;
			ile[dl] = 1;
		}
		else if (result == res[dl]) ile[dl]++;
	}
	for (int i = 1; i <= n; ++i) printf("%d %lld\n", res[i], ile[i]);
	return 0;
}