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
#include <iostream>
#include <vector>
using namespace std;

namespace {

using ll = long long;

struct Counter {
  int inv = 999'999'999;
  ll cnt = 0;

  void update(Counter const& rhs)
  {
    if (rhs.inv < inv) *this = rhs;
    else if (rhs.inv == inv) cnt += rhs.cnt;
  }
};

void go(vector<int> const& perm, vector<Counter>& res, int i, int inv, vector<int>& cur)
{
  int n = perm.size();
  if (i == n) {
    res[cur.size()].update({inv, 1});
    return;
  }
  go(perm, res, i + 1, inv, cur);
  int x = perm[i];
  cur.emplace_back(x);
  for (int y: cur) if (y > x) ++inv;
  go(perm, res, i + 1, inv, cur);
  cur.pop_back();
}

vector<Counter> solve(vector<int> const& perm)
{
  int n = perm.size();

  vector<Counter> res(n + 1);
  res[0] = {0, 1};

  vector<int> cur;
  go(perm, res, 0, 0, cur);

  return res;
}

}

int main()
{
  iostream::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<int> perm(n);
  for (auto& x: perm) {
    cin >> x;
    --x;
  }

  auto res = solve(perm);
  for (int i = 1; i <= n; ++i) {
    cout << res[i].inv << ' ' << res[i].cnt << '\n';
  }

  return 0;
}