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

using namespace std;

struct node {
  int inv;
  long long cnt;

  node(int inv = 1234, long long cnt = 0) : inv(inv), cnt(cnt) {
  }

  node& operator+=(const node& o) {
    if (inv > o.inv) {
      *this = o;
    } else if (inv == o.inv) {
      cnt += o.cnt;
    }
    return *this;
  }
};

struct hash_table {
  static constexpr int P = 4782971;

  int ec, head[P], nxt[P];
  long long to[P];
  node value[P];

  node& operator[](long long v) {
    for (int e = head[v % P]; e; e = nxt[e]) {
      if (to[e] == v) {
        return value[e];
      }
    }
    ++ec;
    to[ec] = v;
    nxt[ec] = head[v % P];
    head[v % P] = ec;
    value[ec] = node();
    return value[ec];
  };

  void clear() {
    for (int e = 1; e <= ec; ++e) {
      head[to[e] % P] = 0;
    }
    ec = 0;
  }
};

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    --a[i];
  }
  a.push_back(n);
  vector<hash_table> dp(2);
  dp[0][0] += node(0, 1);
  for (int i = 0, o = 0; i < n; ++i, o = !o) {
    unordered_map<long long, node> new_dp;
    vector<int> b = a;
    sort(b.begin() + i + 1, b.end());
    int l = 0;
    int r = n;
    for (int j = i + 1; j < n; ++j) {
      if (b[j] < a[i]) {
        l = max(l, b[j] + 1);
      } else {
        r = min(r, b[j]);
      }
    }
    auto skip = [&](long long state, node value) {
      long long mid = (state & ((1ll << r) - 1)) >> l;
      state ^= mid << l;
      state ^= ((1ll << __builtin_popcountll(mid)) - 1) << l;
      dp[!o][state] += value;
    };
    auto take = [&](long long state, node value) {
      value.inv += __builtin_popcountll(state >> a[i]);
      state |= 1ll << a[i];
      skip(state, value);
    };
    for (int e = 1; e <= dp[o].ec; ++e) {
      skip(dp[o].to[e], dp[o].value[e]);
      take(dp[o].to[e], dp[o].value[e]);
    }
    dp[o].clear();
  }
  vector<node> ans(n + 1);
  int o = n & 1;
  for (int e = 1; e <= dp[o].ec; ++e) {
    ans[__builtin_popcountll(dp[o].to[e])] += dp[o].value[e];
  }
  for (int i = 1; i <= n; ++i) {
    cout << ans[i].inv << " " << ans[i].cnt << "\n";
  }
  return 0;
}