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
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=45,M=7000000,K=(1<<20)-1;
int n,i,j,l,r,a[N],cf,cg,ans[N];ll cnt[N],S,nxt,need;char tab[65537];
int c[K+8],q[M],p[M];
struct E{
  ll S,v;
  E(){}
  E(ll _S,ll _v){S=_S,v=_v;}
}f[M],g[M];
inline bool cmp(const E&a,const E&b){return a.S<b.S;}
inline void up(int x,int a,ll b){
  if(ans[x]<a)return;
  if(ans[x]==a)cnt[x]+=b;
  else ans[x]=a,cnt[x]=b;
}
inline void merge(){
  int i,j;
  cf=0;
  for(i=0;i<=K;i++)c[i]=0;
  for(i=1;i<=cg;i++)c[g[i].S&K]++;
  for(i=1;i<=K;i++)c[i]+=c[i-1];
  for(i=1;i<=cg;i++)q[c[g[i].S&K]--]=i;
  for(i=0;i<=K;i++)c[i]=0;
  for(i=1;i<=cg;i++)c[g[i].S>>20]++;
  for(i=1;i<=K;i++)c[i]+=c[i-1];
  for(i=cg;i;i--)p[c[g[q[i]].S>>20]--]=q[i];
  for(i=1;i<=cg;i=j){
    int a=M;ll b=0;
    for(j=i;j<=cg&&g[p[i]].S==g[p[j]].S;j++){
      if((g[p[j]].v&1023)<a)a=g[p[j]].v&1023,b=g[p[j]].v>>10;
      else if((g[p[j]].v&1023)==a)b+=g[p[j]].v>>10;
    }
    f[++cf]=E(g[p[i]].S,b<<10|a);
  }
  cg=0;
}
inline int popcount(ll S){return tab[S&65535]+tab[S>>16&65535]+tab[S>>32];}
inline ll fix(ll S){
  return S^(S&need)^(((1LL<<popcount(S&need))-1)<<l);
}
int main(){
  for(i=0;i<65536;i++)tab[i]=__builtin_popcount(i);
  scanf("%d",&n);
  for(i=1;i<=n;i++)scanf("%d",&a[i]),a[i]--;
  f[cf=1]=E(0,1<<10);
  for(i=1;i<=n;i++){
    S=~0ULL>>1;
    for(j=0;j<=a[i];j++)S^=1LL<<j;
    nxt=0;
    for(j=i+1;j<=n;j++)nxt|=1LL<<a[j];
    for(l=a[i];~l;l--)if(nxt>>l&1)break;
    for(r=a[i];r<n;r++)if(nxt>>r&1)break;
    l++,r--;
    need=0;
    for(j=l;j<=r;j++)need|=1LL<<j;
    for(j=1;j<=cf;j++){
      g[++cg]=E(fix(f[j].S),f[j].v);
      g[++cg]=E(fix(f[j].S|(1LL<<a[i])),f[j].v+popcount(S&f[j].S));
    }
    merge();
  }
  for(i=0;i<=n;i++)ans[i]=M;
  for(i=1;i<=cf;i++)up(popcount(f[i].S),f[i].v&1023,f[i].v>>10);
  for(i=1;i<=n;i++)printf("%d %lld\n",ans[i],cnt[i]);
}