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
#include<bits/stdc++.h>
#define mk make_pair
#define ff first
#define sc second

using namespace std;

const int inf = (1<<30)-1;
const int potm = 64;
const int lim = 49;

int n,tab[lim],tt[potm*2+9];
pair<int,int> wyn[lim];

int main()
{
	scanf("%d", &n);
	for(int i = 0;i<n;++i)
	{
		scanf("%d", &tab[i]);
		wyn[i+1] = mk(inf,0);
	}
	for(int i = 1;i<(1<<n);++i)
	{
		int j = i;
		int h = n-1;
		int w = 0;
		while(j)
		{
			if(j&1)
			{
				int i1 = potm;
				int i2 = potm+tab[h]-1;
				while(i1<i2)
				{
					if(i1&1)
					{
						w += tt[i1];
						++i1;
					}
					if(!(i2&1))
					{
						w += tt[i2];
						--i2;
					}
					i1 >>= 1;
					i2 >>= 1;
				}
				if(i1==i2)
				{
					w += tt[i1];
				}
				i1 = potm+tab[h];
				while(i1)
				{
					++tt[i1];
					i1 >>= 1;
				}
			}
			--h;
			j >>= 1;
		}
		int pc = __builtin_popcount(i);
		if(wyn[pc].ff==w)
		{
			++wyn[pc].sc;
		}
		else
		if(wyn[pc].ff>w)
		{
			wyn[pc] = mk(w,1);
		}
		for(j = potm*2-1;j;--j)
		{
			tt[j] = 0;
		}
	}
	
	for(int i = 1;i<=n;++i)
	{
		printf("%d %d\n", wyn[i].ff, wyn[i].sc);
	}
}