#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " " << x << endl;

const int N = 50, root = 0, LOG = 21;
vector<int> higher, lower, lower_id;
int s1, s2, n, base = root;
pair<int, long long> answer[N];
int pref[N], t[N];


struct node {
    pair<int, int> wyn[LOG]; // pokłucenie, ile
    int dodawacz;
    int lazy; // ile dodac do wyniku
    int sons[LOG];
    int sons_size;
    int l, r;

    node() {
        for(int i = 0; i < LOG; i++) wyn[i] = {1e9, 1};
        for(int i = 0; i < LOG; i++) sons[i] = -1;
        dodawacz = 0;
        lazy = 0;
        sons_size = 0;
        l = LOG;
        r = 0;
    }
};

node tree[(1 << LOG) + 7]; // ? rozmiar

pair<int, int> lamus(const pair<int, int>& a, const pair<int, int>& b) {
    if(a.first > b.first) {
        return b;
    } else if(a.first == b.first) {
        return {a.first, a.second + b.second};
    }
    return a;
}

int licz_inwersje(vector<int> vek, int mask) {
    long long tablica = 0;
    int ret = 0;
    for(int i = (int)vek.size() - 1; i >= 0; i--) {
        if(!(mask & (1 << i))) continue;
        long long tmp = tablica;
        tmp >>= vek[i];
        ret += __builtin_popcount(tmp);
        tablica += (1ll << vek[i]);
    }
    return ret;
}

void fix(int v) {
    if(tree[v].sons_size == 0) return;

    for(int i = tree[v].l; i <= tree[v].r; i++) {
        tree[v].wyn[i] = {1e9, 1};
    }

    for(int i = 0; i < tree[v].sons_size; i++) {
        int x = tree[v].sons[i];

        for(int i = tree[x].l; i <= tree[x].r; i++) {
            int b = tree[x].wyn[i].first + tree[x].lazy;

            if(tree[v].wyn[i].first > b) {
                tree[v].wyn[i].first = b;
                tree[v].wyn[i].second = tree[x].wyn[i].second;
            } else if(tree[v].wyn[i].first == b) {
                tree[v].wyn[i].second += tree[x].wyn[i].second;
            }
        }
    }
}

void create(int v, int mask, int w, int gl, int pop_count) {
    gl --;
    if(gl == -1) {
        tree[v].wyn[pop_count] = lamus(tree[v].wyn[pop_count], {w, 1});
        tree[v].l = min(tree[v].l, pop_count);
        tree[v].r = max(tree[v].r, pop_count);
        return;
    }

    int ile_ja_mam = 0;

    if(tree[v].sons_size == 0) {
        for(int i = 0; i <= lower_id[gl]; i++) {
            tree[v].sons[tree[v].sons_size] = ++base;
            tree[v].sons_size ++;
            tree[base].dodawacz = i;
        }
    }

    for(int i = 0; i < lower_id[gl]; i++) {
        if(mask & 1) ile_ja_mam ++;
        mask /= 2;
    }

    create(tree[v].sons[ile_ja_mam], mask, w, gl, pop_count);
}

void dfs(int v, int gl) {
    gl --;
    if(gl == -1) {
        return;
    }

    for(int i = 0; i < tree[v].sons_size; i++) {
        dfs(tree[v].sons[i], gl);
        tree[v].l = min(tree[v].l, tree[tree[v].sons[i]].l);
        tree[v].r = max(tree[v].r, tree[tree[v].sons[i]].r);
    }
    fix(v);
}

void insert(int v, int suma, int w, int gl, int acc) {
    acc += tree[v].dodawacz;

    gl --;
    if(suma == 0) {
        tree[v].lazy += w * acc;
        return;
    }

    suma -= lower_id[gl];

    for(int i = 0; i < tree[v].sons_size; i++) {
        insert(tree[v].sons[i], suma, w, gl, acc);
    }
    fix(v);
}

void solve() {
    cin >> n;
    if(n < 10) s1 = n / 2; // higher 22
    else s1 = (n + 2) / 2; // higher 21
    s2 = n - s1; // lower

    for(int i = 0; i < n; i++) {
        cin >> t[i];
        if(t[i] > s2) higher.push_back(t[i]);
        else lower.push_back(t[i]);
    }

    for(int i = 0; i <= n; i++) answer[i] = {1e9, 1};

    int cnt_tmp = 0;
    for(int i = n - 1; i >= 0; i--) {
        if(t[i] > s2 and (lower_id.size() == 0 or cnt_tmp != 0)) {
            lower_id.push_back(cnt_tmp);
            cnt_tmp = 0;
        }
        if(t[i] <= s2) {
            cnt_tmp ++;
        }
    }

    reverse(lower_id.begin(), lower_id.end());
    reverse(lower.begin(), lower.end());

    for(int i = 0; i < (1 << s2); i++) {
        create(root, i, licz_inwersje(lower, i), lower_id.size(), __builtin_popcount(i));
    }
    dfs(root, lower_id.size());

    int ktury_odwiedzony = 0;
    int ile_na_pref = 0;

    for(int i = n - 1; i >= 0; i--) {
        if(t[i] > s2) {
            pref[ktury_odwiedzony] = ile_na_pref;
            ktury_odwiedzony ++;
        } else {
            ile_na_pref ++;
        }
    }

    reverse(higher.begin(), higher.end());

    for(int i = 0; i < (1 << s1); i++) {
        if(i != 0) {
            for(int j = 0; j < s1; j++) {
                if((i & (1 << j)) > 0 and ((i - 1) & (1 << j)) == 0) {
                    insert(root, pref[j], 1, lower_id.size(), 0);
                }
                if((i & (1 << j)) == 0 and ((i - 1) & (1 << j)) > 0) {
                    insert(root, pref[j], -1, lower_id.size(), 0);
                }
            }
        }

        node ret = tree[root];

        int cnt = __builtin_popcount(i);
        int ile = licz_inwersje(higher, i);
        for(int j = 0; j <= s2; j++) {

            pair<int, int> b = {ret.wyn[j].first + ile, ret.wyn[j].second};
            if(answer[cnt + j].first > b.first) {
                answer[cnt + j] = b;
            } else if(answer[cnt + j].first == b.first) {
                answer[cnt + j].second += b.second;
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        cout << answer[i].first << " " << answer[i].second << endl;
    }
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int test = 1;

	while(test--){
		solve();
	}

	return 0;
}