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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int,int>> v;
int n,a,wyn, CL;

int N[32];
int ile[32];
int best[32];
int perm[32];

int main()
{
	//n = 29;
	scanf("%d", &n);

	for(int i = 0; i <= n; i++) perm[i] = i;
	random_shuffle(perm + 1, perm + n + 1);

	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a);
		//a = perm[i];
		v.emplace_back(a, i);
	}



	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(v[i].first < v[j].first && v[i].second < v[j].second)
			{
				N[i] |= (1ll << j);
				N[j] |= (1ll << i);
			}
		}
	}

	int MASK = 0;
	int K = 0;
	int wyn = 0;
	int mov, boi;
	int LIM = (1ll << n);
	bool negate;

	for(int I = 1; I ^ LIM; ++I)
	{
		mov = I & (-I);
		boi = __builtin_ctz(mov);
		MASK ^= mov;

		negate = !(MASK & mov);
		K += (1 ^ -negate) + negate;
		wyn += (__builtin_popcount(N[boi] & MASK) ^ -negate) + negate;


		if(wyn >= best[K])
		{
			if(wyn > best[K])
			{
				best[K] = wyn;
				ile[K] = 0;
			}
			++ile[K];
		}
	}

	for(int i = 1; i <= n; i++)
	{
		printf("%d %d\n", i * (i - 1) / 2 - best[i], ile[i]);
	}
}