#include <bits/stdc++.h>
using namespace std;
const int MX=(1<<20);
int n,n2,i,a[42],b[42],c[MX],r[42];
long long x[42],res[42];
void rec(int l, int cnt, int inv, long long mask) {
  if (inv>r[n-l+cnt]) return;
  if (l==n) {
    if (inv<r[cnt]) {
      r[cnt]=inv;
      res[cnt]=1;
    } else ++res[cnt];
    return;
  }
  int cur=(b[l]<=n2)?c[x[l]&mask]:(cnt-c[mask>>b[l]]);
  rec(l+1,cnt+1,inv+cur,mask|(1LL<<b[l]));
  rec(l+1,cnt,inv,mask);
}
int main() {
  for (i=1; i<MX; i++) c[i]=c[i/2]+(i&1);
  scanf("%d",&n); n2=n/2;
  for (i=1; i<=n; i++) r[i]=n*n;
  for (i=0; i<n; i++) {
    scanf("%d",&a[i]);
    b[n-a[i]]=i;
    x[n-a[i]]=(1LL<<i)-1;
  }
  rec(0,0,0,0);
  for (i=1; i<=n; i++) cout<<r[i]<<' '<<res[i]<<'\n';
  return 0;
}