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

int n,t[34],a[34],p[34],w[34];

long long z[34];

int marge_sort(int l,int r)
{
    if(l == r) return 0;
    int m = (l + r) >> 1;
    int W = marge_sort(l,m) + marge_sort(m + 1,r);
    int i = l,j = m + 1,poz = l;
    while(poz <= r)
    {
        if(j > r || (i <= m && a[i] <= a[j])) p[poz] = a[i++];
        else
        {
            p[poz] = a[j++];
            W += m - i + 1;
        }
        poz++;
    }
    for(int i = l;i <= r; ++i) a[i] = p[i];
    return W;
}

int main()
{
    ios_base::sync_with_stdio(0);
    
    cin>>n;
    for(int i = 0;i < n; ++i) 
    {
        cin>>t[i];
        w[i + 1] = 1e6;
    }
    int x = 1 << n;
    for(int i = 1;i < x; ++i)
    {
        int k = 0;
        for(int j = 0;j < n; ++j)
            if(i & (1 << j)) a[k++] = t[j];
        int inw = marge_sort(0,k - 1);
        
        if(w[k] > inw)
        {
            w[k] = inw;
            z[k] = 1;
        }
        else if(w[k] == inw) z[k]++;
    }
    for(int i = 1;i <= n; ++i)
        cout<<w[i]<<" "<<z[i]<<'\n';
    return 0;
}