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
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
#define mp make_pair
#define f first
#define s second
using namespace std;
int baza=64,drz[1005],n,t[65],x,ind,wynik,m[65],w[65];
void dodaj(int y,int wsp)
{
y+=baza;
while(y)
    {
    drz[y]+=wsp;
    y/=2;
    }
}
int que(int a,int b,int lo,int hi,int v)
{
if(hi<a||lo>b)return 0;
else if(lo>=a&&hi<=b)return drz[v];
else return que(a,b,lo,(lo+hi)/2,2*v)+que(a,b,(lo+hi)/2+1,hi,2*v+1);
}
int main()
{
ios_base::sync_with_stdio(0);
cin>>n;
for(int i=0;i<n;i++)
    {
    cin>>t[i];
    m[i+1]=100;
    }
for(int i=1;i<(1<<n);i++)
{
x=i-1;
ind=0;
while(true)
    {
    if(x%2)
        {
        if(t[ind]!=1)wynik-=que(1+baza,t[ind]-1+baza,baza,2*baza-1,1);
        dodaj(t[ind],-1);
        //cout<<"USUNIETO "<<ind<<'\n';
        x/=2;
        ind++;
        }
    else
        {
        if(t[ind]!=1)wynik+=que(1+baza,t[ind]-1+baza,baza,2*baza-1,1);
        dodaj(t[ind],1);
        //cout<<"DODANO "<<ind<<'\n';
        break;
        }
    }
//cout<<i<<' '<<wynik<<'\n';
int liczba=__builtin_popcount(i);
if(m[liczba]>wynik)
    {
    m[liczba]=wynik;
    w[liczba]=1;
    }
else if(m[liczba]==wynik)w[liczba]++;
}
for(int i=1;i<=n;i++)cout<<m[i]<<' '<<w[i]<<'\n';
/*cin>>zapy;
while(zapy--)
    {
    zlicz.clear();
    while(!qmax.empty())qmax.pop();
    while(!qmin.empty())qmin.pop();
    wyn1=0;
    wyn2=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        {
        cin>>a>>b>>c;
        if(zlicz[b]==0){qmax.push(b);qmin.push(-b);}
        zlicz[b]+=a;
        if(zlicz[c]==0){qmax.push(c);qmin.push(-c);}
        zlicz[c]-=a;
        wyn1+=a*b;
        wyn2+=a*c;
        }
    cout<<wyn1<<' '<<wyn2;
    if(wyn1==wyn2)
        {
        nie=0;
        while(!qmax.empty())
            {
            if(zlicz[qmax.top()]==0)qmax.pop();
            else if(zlicz[qmax.top()]<0)
                {
                nie=1;
                break;
                }
            else break;
            }
        while(!qmin.empty())
            {
            if(zlicz[-qmin.top()]==0)qmin.pop();
            else if(zlicz[-qmin.top()]<0)
                {
                nie=1;
                break;
                }
            else break;
            }
        if(nie)cout<<"NIE"<<'\n';
        else cout<<"TAK"<<'\n';
        }
    else cout<<"NIE"<<'\n';
    }
*/
}