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>
using namespace std;
typedef long long ll;
typedef pair <int, ll> pill;

const int N = 40;
const ll INF = 1e18;

int n, k;
ll res;
int tab[N + 5];
pill ans[N + 5];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> tab[i];
		ans[i].second = INF;
	}
	for(ll i=0ll; i<(1ll << n); i++){
		k = __builtin_popcount(i);
		
		res = 0;
		for(ll j=0ll; j<n; j++){
			if((i >> j) & 1ll){
				for(int h=0; h<j; h++){
					if((i >> h) & 1ll){
						res += (tab[h] > tab[j]);
					}
				}
			}
		}
		if(k == 1){
		//	cout << i << " : " << res << "\n";
		}
		if(ans[k].second > res){
			ans[k] = {0, res};
		}
		if(ans[k].second == res){
			ans[k].first ++;
		}
	}
	for(int i=1; i<n; i++){
		cout << ans[i].second << " " << ans[i].first << "\n";
	}
	res = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<i; j++){
			res += (tab[j] > tab[i]);
		}
	}
	cout << res << " " << 1 << "\n";
	
	return 0;
}