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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// Author: Kamil Nizinski
// NOLINT(legal/copyright)
#ifdef LOCAL
#ifdef COLOR
#include "bits/cp_local_color.h"
#else
#include "bits/cp_local.h"
#endif
#else
#include "bits/stdc++.h"
#define debug_arr(arr_name, first, last)
#define debug(...)
#define cerr if (false) cerr
#define speed_of_cin_and_cout ios_base::sync_with_stdio(0), cin.tie(0)
#define local if (false)
#endif
#define ft first
#define sd second
#define psb push_back
#define sz(a) (static_cast<int>((a).size()))
using namespace std;  // NOLINT(build/namespaces)
typedef int64_t LL;
typedef uint64_t LLU;
typedef long double LD;
typedef pair<int, int> PII;
const int kInf = 1000000007;

void solve64(int *a, int n) {
  LLU inverses_with[n];
  for (int i = 0; i < n; i++) {
    inverses_with[i] = LLU{0};
    for (int j = 0; j < i; j++)
      if (a[j] > a[i]) inverses_with[i] |= (LLU{1} << j);
    for (int j = i + 1; j < n; j++)
      if (a[i] > a[j]) inverses_with[i] |= (LLU{1} << j);
  }
  int sub_from_63[65];
  for (int i = 0; i < 65; i++)
    sub_from_63[i] = 63 - i;
  debug((LLU{1} << n));
  int best_scores[n + 1];
  LLU ways_nums[n + 1];
  for (int k = 1; k <= n; k++)
    best_scores[k] = kInf;
  best_scores[0] = 0;
  ways_nums[0] = LLU{1};
  LLU previous_Gray_code = LLU{0};
  int previous_score = 0;
  // LLU previous_ways_num = LLU{1};
  cerr << "Check 1\n";
  LLU end = (LLU{1} << n);
  for (LLU mask = LLU{1}; mask != end; mask++) {
    LLU current_Gray_code = mask ^ (mask >> 1);
    LLU the_difference = previous_Gray_code ^ current_Gray_code;
    int index_switched = sub_from_63[__builtin_clzll(the_difference)]; //  64 - __builtin_clzll(the_difference) - 1;
    int current_score = previous_score;
    if (previous_Gray_code < current_Gray_code) {
      current_score += __builtin_popcountll(inverses_with[index_switched] & previous_Gray_code);
    } else {
      current_score -= __builtin_popcountll(inverses_with[index_switched] & previous_Gray_code);
    }
    int k = __builtin_popcountll(current_Gray_code);
    if (current_score == best_scores[k]) {
      ways_nums[k]++;
    } else {
      if (current_score < best_scores[k]) {
        best_scores[k] = current_score;
        ways_nums[k] = LLU{1};
      }
    }
    previous_Gray_code = current_Gray_code;
    previous_score = current_score;
  }
  for (int k = 1; k <= n; k++) {
    cout << best_scores[k] << " " << ways_nums[k] << "\n";
  }
  cerr << "Finished.\n";
}

void solve32(int *a, int n) {
  uint32_t inverses_with[n];
  for (int i = 0; i < n; i++) {
    inverses_with[i] = uint32_t{0};
    for (int j = 0; j < i; j++)
      if (a[j] > a[i]) inverses_with[i] |= (uint32_t{1} << j);
    for (int j = i + 1; j < n; j++)
      if (a[i] > a[j]) inverses_with[i] |= (uint32_t{1} << j);
  }
  int sub_from_31[33];
  for (int i = 0; i < 33; i++)
    sub_from_31[i] = 31 - i;
  int best_scores[n + 1];
  uint32_t ways_nums[n + 1];
  for (int k = 1; k <= n; k++)
    best_scores[k] = kInf;
  best_scores[0] = 0;
  ways_nums[0] = uint32_t{1};
  uint32_t previous_Gray_code = uint32_t{0};
  int previous_score = 0;
  // uint32_t previous_ways_num = uint32_t{1};
  cerr << "Check 1\n";
  uint32_t end;
  if (n == 32) end = uint32_t{0};
  else end = (uint32_t{1} << n);
  debug(end);
  for (uint32_t mask = uint32_t{1}; mask != end; mask++) {
    uint32_t current_Gray_code = mask ^ (mask >> 1);
    uint32_t the_difference = previous_Gray_code ^ current_Gray_code;
    int index_switched = sub_from_31[__builtin_clz(the_difference)]; //  64 - __builtin_clzll(the_difference) - 1;
    int current_score = previous_score;
    if (previous_Gray_code < current_Gray_code) {
      current_score += __builtin_popcount(inverses_with[index_switched] & previous_Gray_code);
    } else {
      current_score -= __builtin_popcount(inverses_with[index_switched] & previous_Gray_code);
    }
    int k = __builtin_popcount(current_Gray_code);
    if (current_score == best_scores[k]) {
      ways_nums[k]++;
    } else {
      if (current_score < best_scores[k]) {
        best_scores[k] = current_score;
        ways_nums[k] = uint32_t{1};
      }
    }
    previous_Gray_code = current_Gray_code;
    previous_score = current_score;
  }
  for (int k = 1; k <= n; k++) {
    cout << best_scores[k] << " " << ways_nums[k] << "\n";
  }
  cerr << "Finished.\n";
}

int main() {
  speed_of_cin_and_cout;
  int test_cases_num = 1;
//   cin >> test_cases_num;
  for (int i = 1; i <= test_cases_num; i++) {
    local if (test_cases_num > 1) cerr << "Test #" << i << ":\n";
    int n;
    cin >> n;
    int a[n];
    for (int j = 0; j < n; j++) {
      cin >> a[j];
      a[j]--;
    }
    if (n <= 32) solve32(a, n);
    else solve64(a, n);
    local if (test_cases_num > 1) cerr << "End of test #" << i << ".\n";
  }
  return 0;
}