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
#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
 
constexpr int inf = 0x3f3f3f3f;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
    vector<int> a(n);
    for(int &ai : a) {
        cin >> ai;
        --ai;
    }
 
    vector<vector<bool>> normalgraph(n, vector<bool>(n)), antigraph = normalgraph;
    REP(i, n)
        FOR(j, i + 1, n - 1)
            if(a[i] > a[j])
                normalgraph[i][j] = normalgraph[j][i] = true;
            else
                antigraph[i][j] = antigraph[j][i] = true;

	vector<int> antiperm = a;
	REP(i, n)
		antiperm[i] = n - 1 - a[i];
 
    auto lis = [&](vector<int> &perm) {
        vector<int> dp(n, 1);
        REP(i, n)
            REP(j, i)
                if(perm[j] < perm[i])
                    dp[i] = max(dp[i], dp[j] + 1);
        int i = int(max_element(dp.begin(), dp.end()) - dp.begin());
        vector<int> ret = {i};
        while(dp[i] > 1) {
			int j = 0;
			while(j < i and (dp[j] != dp[i] - 1 or perm[j] > perm[i]))
				++j;
			assert(j < i);
			i = j;
            ret.emplace_back(i);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    };
 
    vector<int> independent_normal = lis(a), independent_anti = lis(antiperm);
	int s1 = int(independent_normal.size()), s2 = int(independent_anti.size());
	int type = s1 < s2;
	vector<int> independent = type ? independent_anti : independent_normal;
	int indep_size = int(independent.size());
	// cerr << indep_size << ' ';
	vector<vector<bool>> graph = type ? antigraph : normalgraph;

	vector<bool> inside_mask(n, true);
	for(int v : independent)
		inside_mask[v] = false;
	vector<int> to_mask;
	REP(v, n)
		if(inside_mask[v])
			to_mask.emplace_back(v);
	int tm = int(to_mask.size());

	vector<vector<LL>> dwumian(n + 1, vector<LL>(n + 1));
	REP(i, n + 1)
		dwumian[i][0] = dwumian[i][i] = 1;
	FOR(i, 1, n)
		FOR(j, 1, n)
			dwumian[i][j] = dwumian[i - 1][j - 1] + dwumian[i - 1][j];

	vector<pair<int, LL>> answer(n + 1, {inf, 0});

	REP(mask, 1 << tm) {
		int popc = __builtin_popcount(mask);
		vector<int> inside;
		inside.reserve(popc);
		REP(i, tm)
			if(mask & (1 << i))
				inside.emplace_back(to_mask[i]);

		int score = 0;
		for(int i = 0; i < popc; ++i)
			for(int j = i + 1; j < popc; ++j)
				score += graph[inside[i]][inside[j]];

		vector<int> contributon(indep_size);
		for(int i = 0; i < popc; ++i)
			for(int j = 0; j < indep_size; ++j)
				if(graph[inside[i]][independent[j]])
					++contributon[j];

		vector<int> sorted(popc + 1);
		for(int c : contributon)
			++sorted[c];
		vector<int> remaining = sorted;
		int i = type ? popc : 0;

		FOR(k, popc, popc + indep_size) {
			if(k != popc) {
				while(remaining[i] == 0) {
					if(type == 0)
						++i;
					else
						--i;
				}
				score += i;
				--remaining[i];
			}

			if(type == 1)
				score = k * (k - 1) / 2 - score;
			if(answer[k].first > score) {
				answer[k].first = score;
				answer[k].second = dwumian[sorted[i]][remaining[i]];
			}
			else if(answer[k].first == score)
				answer[k].second += dwumian[sorted[i]][remaining[i]];
			if(type == 1)
				score = k * (k - 1) / 2 - score;
		}
	}

	FOR(i, 1, n)
		cout << answer[i].first << ' ' << answer[i].second << '\n';
}