#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define fi first
#define sc second
#define mkp make_pair
#define pii pair<int,int>
typedef long long ll;
#define pil pair<int,ll>
const int N=45,K=(1<<21)+5,M=8e6+5,oo=1e9,bas=131,mod=1e9+9;
inline int read() {
    int x=0,flag=0;char ch=getchar();
    while(ch<'0'||ch>'9') {flag|=(ch=='-');ch=getchar();}
    while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return flag?-x:x;
}
inline int mx(int x,int y) {return x>y?x:y;}
inline int mn(int x,int y) {return x<y?x:y;}
inline void swp(int &x,int &y) {x^=y^=x^=y;}
inline int as(int x) {return x>0?x:-x;}

int n,a[N],f[K];
pil ans[N];
inline void FWT(int*f,int n) {
    for(int i=0;i<n;++i) 
        for(int j=0;j<(1<<n);++j)
            if((j>>i)&1)
                f[j]+=f[j^(1<<i)];
}
namespace sub1 {
    inline void solve() {
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j)
                if(a[i]>a[j]) f[(1<<i)|(1<<j)]=1;
        FWT(f,n);
        for(int i=0;i<=n;++i) ans[i]=mkp(oo,0);
        for(int i=0,len;i<(1<<n);++i) {
            len=__builtin_popcount(i);
            if(f[i]<ans[len].fi) ans[len]=mkp(f[i],1ll);
            else if(f[i]==ans[len].fi) ++ans[len].sc;
        }
        for(int i=1;i<=n;++i) printf("%d %lld\n",ans[i].fi,ans[i].sc);
    }
}
namespace sub2 {
    int A[N],A_[N],tot,col[N],t[N],T[N];
    int vc[2][M],cnt[2],pre[20],god;
    pil F[2][M];
    inline void solve() {
        for(int i=21;i<n;++i) A[tot]=A_[tot]=a[i],++tot;
        sort(A_,A_+tot);
        for(int i=0;i<tot;++i) A[i]=lower_bound(A_,A_+tot,A[i])-A_;
        for(int i=0;i<21;++i) col[i]=lower_bound(A_,A_+tot,a[i])-A_,++t[col[i]];
        for(int i=0;i<21;++i)
            for(int j=i+1;j<21;++j)
                if(a[i]>a[j])f[(1<<i)|(1<<j)]=1;
        FWT(f,21);
        god=0;cnt[0]=1;for(int i=0;i<=tot;++i) cnt[god]*=(t[i]+1);
        for(int i=0;i<cnt[0];++i) F[0][i]=mkp(oo,0);
        for(int i=0,Sum;i<(1<<21);++i) {
            int qwq=0;
            for(int j=0;j<21;++j)
                if((i>>j)&1) ++pre[col[j]],++qwq;
            Sum=0;
            for(int j=0;j<=tot;++j)
                Sum=Sum*(t[j]+1)+pre[j],
                pre[j]=0;
            if(f[i]<F[0][Sum].fi) F[0][Sum]=mkp(f[i],1ll);
            else if(f[i]==F[0][Sum].fi) ++F[0][Sum].sc;
        }
        for(int o=21;o<n;++o) {
            god=(o&1);cnt[god]=1;
            int fro=A[0];
            tot=0;
            for(int i=o+1;i<n;++i) A[tot]=A_[tot]=a[i],++tot;
            sort(A_,A_+tot);
            for(int i=0;i<tot;++i) A[i]=lower_bound(A_,A_+tot,A[i])-A_;
            for(int i=0;i<=o;++i) col[i]=lower_bound(A_,A_+tot,a[i])-A_,++T[col[i]];
            for(int i=0;i<=tot;++i) cnt[god]*=(T[i]+1);
            for(int i=0;i<cnt[god];++i) F[god][i]=mkp(oo,0);
            for(int i=0,Sum,del;i<cnt[god^1];++i) {
                Sum=i;
                for(int j=tot+1;j>=0;--j)
                    pre[j]=Sum%(t[j]+1),Sum/=(t[j]+1);
                pre[fro]+=pre[fro+1];del=pre[fro+1];
                for(int j=fro+1;j<=tot;++j) pre[j]=pre[j+1],del+=pre[j];
                Sum=0;
                for(int j=0;j<=tot;++j)
                    Sum=Sum*(T[j]+1)+pre[j];
                if(F[god^1][i].fi<F[god][Sum].fi) F[god][Sum]=F[god^1][i];
                else if(F[god^1][i].fi==F[god][Sum].fi) F[god][Sum].sc+=F[god^1][i].sc;
                ++pre[fro]; Sum=0;
                for(int j=0;j<=tot;++j)
                    Sum=Sum*(T[j]+1)+pre[j];
                F[god^1][i].fi+=del;
                if(F[god^1][i].fi<F[god][Sum].fi) F[god][Sum]=F[god^1][i];
                else if(F[god^1][i].fi==F[god][Sum].fi) F[god][Sum].sc+=F[god^1][i].sc;
            }
            for(int i=0;i<=tot+1;++i) t[i]=T[i],T[i]=0;
        }
        for(int i=1;i<=n;++i)
            printf("%d %lld\n",F[(n-1)&1][i].fi,F[(n-1)&1][i].sc);
    }
}
int main() {
    n=read();
    for(int i=0;i<n;++i) a[i]=read();
    if(n<=21) sub1::solve();
    else sub2::solve();
    return 0;
}