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
#include <bits/stdc++.h>

using namespace std;

int a[50];
int a_inv[135000005];
int res[50];
int cnt[50];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];

    for(int i=0;i<=n;i++)res[i]=1e9;
    for(int i=1;i<(1<<n);i++)
    {
        int last=__builtin_ctz(i);
        int j=(i^(1<<last));
        a_inv[i]=a_inv[j];
        for(int k=0;k<n;k++)if((j&(1<<k))!=0&&a[last]>a[k])a_inv[i]++;
    //    cout<<" "<<i<<" "<<a_inv[i]<<endl;
        if(res[__builtin_popcount(i)]==a_inv[i])cnt[__builtin_popcount(i)]++;
        else if(res[__builtin_popcount(i)]>a_inv[i])res[__builtin_popcount(i)]=a_inv[i], cnt[__builtin_popcount(i)]=1;
    }

    for(int i=1;i<=n;i++)cout<<res[i]<<" "<<cnt[i]<<endl;
}