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 <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 42;

struct hsh {
  ll operator() (const vector <int> &a) const {
    ll h = 0;
    for (int x : a) h = h * 40 + x;
    return h;
  }
};

unordered_map <vector <int>, pair <int, ll>, hsh> mp[N][N];

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector <int> perm(n);
  for (int i = 0; i < n; i++) {
    cin >> perm[i];
  }
  vector <int> arr(n);
  mp[0][0][arr] = make_pair(0, 1ll);
  auto relax = [&] (int i, int j, vector <int> t, pair <int, ll> cur) {
    if (!mp[i][j].count(t)) {
      mp[i][j][t] = cur;
    } else {
      if (mp[i][j][t].first < cur.first) {
        return;
      }
      if (mp[i][j][t].first == cur.first) {
        mp[i][j][t].second += cur.second;
      } else {
        mp[i][j][t] = cur;
      }
    }
  };
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
      for (auto c : mp[i][j]) {
        auto go = c.first;
        auto p = c.second;
        p.first += go[i];
        go[i] = 0;
        relax(i + 1, j, go, c.second);
        for (int j = i + 1; j < n; j++) if (perm[j] < perm[i]) go[j]++;
        relax(i + 1, j + 1, go, p);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << mp[n][i][arr].first << ' ' << mp[n][i][arr].second << '\n';
  }
}