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
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

struct Foo {
  int res;
  ll count, mask;
  Foo(int _res = 0, ll _count = 0, ll _mask = 0)
    : res(_res), count(_count), mask(_mask) {}
};

vector<vector <Foo>> tmp, tmp2;

int main() {
  ios_base::sync_with_stdio(0);
  int n;
  cin >> n;
  int M = (n+1)/2;
  vector <int> a;
  for(int i=0; i<n; i++) {
    int x;
    cin >> x;
    a.push_back(x-1);
  }
  vector <Foo> dp{Foo(0,1LL,0LL)};
  vector <vector<Foo>> tmp(1<<M), tmp2(1<<M);
  ll taken = 0;
  for(int i=0; i<n; i++) {
    taken |= (1LL << a[i]);
    int lef, rig;
    for(lef = a[i]; lef >= 0; lef--) {
      if(((taken >> (lef-1)) & 1) == 0) break;
    }
    for(rig = a[i]+1; rig < n; rig++) {
      if(((taken >> rig) & 1) == 0) break;
    }
    long long blocked = ((1LL << (rig-lef)) - 1) << lef;
    for(auto ele : dp) {
      ll disabled = (ele.mask & blocked), enabled = (ele.mask & ~blocked);
      ll new_mask = enabled | (((1LL << __builtin_popcountll(disabled))-1) << lef);
      ll other_mask = new_mask | (1LL << (__builtin_popcountll(disabled) + lef));
      tmp[new_mask & ((1<<M)-1)].emplace_back(ele.res, ele.count, new_mask);
      tmp[other_mask & ((1<<M)-1)].emplace_back(
        ele.res + __builtin_popcountll(((1LL << n) - (1LL << a[i])) & ele.mask),
        ele.count, other_mask);
    }
    for(auto& vec : tmp) {
      while(!vec.empty()) {
        tmp2[vec.back().mask >> M].push_back(vec.back());
        vec.pop_back();
      }
      vec.shrink_to_fit();
    }
    dp.clear();
    for(auto& vec2 : tmp2) {
      while(!vec2.empty()) {
        auto ele = vec2.back();
        if(dp.empty()) dp.push_back(ele);
        else {
          if(dp.back().mask != ele.mask) dp.push_back(ele);
          else {
            if(dp.back().count == 0  or dp.back().res > ele.res) dp.back() = ele;
            else if(dp.back().res == ele.res) dp.back().count += ele.count;
          }
        }
        vec2.pop_back();
      }
      vec2.shrink_to_fit();
    }
  }
  vector <Foo> ret(n);
  for(auto ele : dp) {
    int ones = __builtin_popcountll(ele.mask) - 1;
    if(not(0 <= ones and ones < n)) continue;
    if(ret[ones].count == 0 or ret[ones].res > ele.res) ret[ones] = ele;
    else if(ret[ones].res == ele.res) ret[ones].count += ele.res;
  }
  for(int i=0; i<n; i++) {
    cout << ret[i].res << " " << ret[i].count << "\n";
  }
}