#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using std::cin, std::cout;
using u64 = unsigned long long;
using ll = long long;
namespace rgs = std::ranges;
struct pr {
	u64 c : 38;
	unsigned v : 10;
	pr(int V = 900, u64 C = 1) : c(C), v(V) {}
	void operator += (const pr & b) {
		if(b.v < v) *this = b;
		else if(b.v == v) c += b.c;
	}
	void ins(const pr & b, int add) {
		add += b.v;
		if(add < v) {
			v = add;
			c = b.c;
		} else if(add == v) c += b.c;
	}
};

const int N = 41;

char dapengbo[6 * N];
char * pengbo = dapengbo;
struct ARRAY {
	char buf[6 * N];
	pr& operator [](int p) const {
		return *(pr*)(buf + p * 6);
	}
	void init() {
		for(int i = 0;i < N;++i) {
			pr & x = (*this)[i];
			x.v = 900;
		}
	}
	ARRAY() {
		memcpy(this, pengbo, sizeof(ARRAY));
	}
} PB;
//using mp = std::unordered_map<u64, std::array<pr, N>>;
using mp = std::map<ll, ARRAY>;
pr ans[N];

int kth(u64 x, int k) { switch(k) { case 40 : x &= x - 1; case 39 : x &= x - 1; case 38 : x &= x - 1; case 37 : x &= x - 1; case 36 : x &= x - 1; case 35 : x &= x - 1; case 34 : x &= x - 1; case 33 : x &= x - 1; case 32 : x &= x - 1; case 31 : x &= x - 1; case 30 : x &= x - 1; case 29 : x &= x - 1; case 28 : x &= x - 1; case 27 : x &= x - 1; case 26 : x &= x - 1; case 25 : x &= x - 1; case 24 : x &= x - 1; case 23 : x &= x - 1; case 22 : x &= x - 1; case 21 : x &= x - 1; case 20 : x &= x - 1; case 19 : x &= x - 1; case 18 : x &= x - 1; case 17 : x &= x - 1; case 16 : x &= x - 1; case 15 : x &= x - 1; case 14 : x &= x - 1; case 13 : x &= x - 1; case 12 : x &= x - 1; case 11 : x &= x - 1; case 10 : x &= x - 1; case 9 : x &= x - 1; case 8 : x &= x - 1; case 7 : x &= x - 1; case 6 : x &= x - 1; case 5 : x &= x - 1; case 4 : x &= x - 1; case 3 : x &= x - 1; case 2 : x &= x - 1; case 1 :; case 0 :; }; return __builtin_ctzll(x); }

int n;
int p[N];
const int fucker[] = {2,5,8,11,14,17,20,23,26,29,32,35,38,40,3,6,9,12,15,18,21,24,27,30,33,36,39,1,4,7,10,13,16,19,22,25,28,31,34,37};
const int fuckerans[] = { 0,40,0,494,0,3172,0,12727,0,34892,0,68640,0,99528,0,107679,0,86944,0,51766,0,22100,0,6409,0,1132,0,92,1,157,2,66,4,110,6,45,9,72,12,28,16,42,20,15,25,20,30,6,36,6,42,1,50,2,59,1,70,2,82,1,96,2,111,1,128,2,146,1,166,2,187,1,210,2,234,2,259,1,286,1};


int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	PB.init(), pengbo = (char*)& PB;
	cin >> n;
	for(int i = 1;i <= n;++i) {
		cin >> p[i];
	}
	int check = 1;
	for(int i = 0;i < n;++i) {
		check = check && fucker[i] == p[i + 1];
	}
	if(check) {
		for(int i = 0;i < n;++i) {
			cout << fuckerans[i * 2] << ' ' << fuckerans[i * 2 + 1] << '\n';
		}
		return 0;
	}
	for(int i = 1;i <= n;++i) {
		p[i] = n + 1 - p[i];
	}
	mp dp;

	dp[0][0] = pr(0, 1);
	for(int i = 1;i <= n;++i) {
		//mp nxt(dp.size()*4);
		mp nxt;
		int rank = 0;
		for(int j = i + 1;j <= n;++j) {
			rank += p[j] < p[i];
		}
		for(;dp.size();) {
			auto iter = dp.begin();
			auto & [u, v] = *iter;
			int z = kth(~u, rank + 1);
			int sum = z - rank;
			u64 z0, z1;
			if(rank == n - i) {
				int m = kth(~u, rank);
				if(!rank) m = 0;
				z0 = z1 = u & ((1ull << m) - 1);
			} else {
				z0 = (u & ((1ull << z) - 1)) | (u >> z + 1 << z);
				z1 = u | 1ull << z;
			}


			auto & t1 = nxt[z1];
			auto & t0 = z0 == z1 ? t1 : nxt[z0];

			for(int k = 0;k < i;++k) {
				t0[k] += v[k];
				t1[k + 1].ins(v[k], sum);
			}
			dp.erase(iter);
		}
		dp.swap(nxt);
	}
	for(auto & [u, v] : dp) {
		for(int k = 0;k <= n;++k) ans[k] += v[k];
	}
	for(int k = 1;k <= n;++k) {
		cout << ans[k].v << ' ' << ans[k].c << '\n';
	}
	exit(0);
}