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

using namespace std;

struct sol{
    uint64_t number;
    int inversions;
};

class cmp 
{
public:
    bool operator() (sol a, sol b)
    {
        return (a.inversions > b.inversions);
    }
};

int counts[41][40*40*2];

int main(){
    int n ;

    cin >> n;

    vector<int> soldiers;

    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        soldiers.push_back(tmp);
    }


    priority_queue<sol, vector<sol>, cmp> pq;
    for(int j = 0; j < n; j++){
        sol cur;
        cur.inversions = 0;
        cur.number = 1 << j;
        pq.push(cur);
    }

    for(uint64_t i = 1; i < (1ll << n); i ++){
        int inversions = 0;
        for(uint64_t j = 0 ; j < n; j++){
            for(uint64_t k = 0 ; k < n; k++){
                if((i & (1 << j)) && (i & (1 << k)) && ((j < k && soldiers[j] > soldiers[k] ) || (j > k && soldiers[j] < soldiers[k]))){
                    inversions ++;
                } 
            }
        }

        counts[__builtin_popcountll(i)][inversions]++;
    }
    for(int i = 0; i <= n; i ++){
        int j = 0; 
        while(counts[i][j] == 0){
            j++;
        }
        cout << j << " " << counts[i][j] << endl;
    }
}