#include <bits/stdc++.h>
using namespace std;
const int N = 55, M = 5e6 + 7;
bool fl[N];
int n, p[N], f[N], gt[N][N], og[N], pos[N], siz[N], len[N][N];
long long w[2][M], g[2][M];
int main() {
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> p[i], f[p[i]] = i;

    for (int i = 1; i <= n; i++) {
        fl[f[i]] = 1, siz[i] = 1;

        for (int x = 1; x <= n; x++) {
            if (!fl[x])
                continue;

            int c = x;

            while (fl[c + 1] && c < n)
                c++;

            len[i][++len[i][0]] = c - x + 1, siz[i] = siz[i] * (c - x + 2), x = c;
        }
    }

    g[1][0] = 1, g[1][1] = 1;

    for (int i = 1; i <= n; i++) {
        gt[i][len[i][0]] = 1;

        for (int x = len[i][0]; x >= 1; x--)
            gt[i][x - 1] = gt[i][x] * (len[i][x] + 1);
    }

    memset(fl, 0, sizeof(fl));
    fl[f[1]] = 1;

    for (int i = 2; i <= n; i++) {
        memset(og, 0, sizeof(og));
        int f1 = 0, f2 = 0, f3 = 0, tg = 0, ht = 0;
        fl[f[i]] = 1;

        if (!fl[f[i] - 1])
            tg++;

        for (int x = 1; x < f[i]; x++)
            if (fl[x])
                f1 = 1;

        if (fl[f[i] + 1])
            f1 = 1;

        for (int x = f[i] + 1; x <= n; x++)
            if (fl[x])
                f2 = 1;

        if (fl[f[i] - 1])
            f2 = 1;

        if (fl[f[i] - 1] || fl[f[i] + 1])
            f3 = 1;

        for (int x = 1; x <= n; x++) {
            if (!fl[x])
                continue;

            int c = x;

            while (fl[c + 1])
                c++;

            x = c, ht++;

            if (x >= f[i])
                break;
        }

        for (int x = 0; x < siz[i]; x++)
            w[i & 1][x] = 19260817;

        int f = 1, rt = gt[i][len[i][0]], of = len[i][0];

        if (!f1) {
            rt = gt[i][1], of = 0;

            for (int x = 1; x <= len[i - 1][0]; x++)
                pos[x] = x + 1;
        } else if (!f2) {
            rt = 1, of = 19260817;

            for (int x = 1; x <= len[i - 1][0]; x++)
                pos[x] = x;
        } else if (!f3) {
            rt = gt[i][ht], of = ht - 1;

            for (int x = 1; x < ht; x++)
                pos[x] = x;

            for (int x = ht; x <= len[i - 1][0]; x++)
                pos[x] = x + 1;
        } else {
            for (int x = 1; x <= len[i - 1][0]; x++) {
                if (len[i - 1][x] == len[i][f])
                    pos[x] = f++;
                else {
                    pos[x] = pos[x + 1] = f++, rt = gt[i][f - 1], of = f - 1 - tg;

                    if (len[i][x] - len[i - 1][x] > 1)
                        x++;
                }
            }
        }

        int vas = 0, ft = 0;

        for (int x = 0; x < siz[i - 1]; x++) {
            if (w[i & 1][vas] == w[(i & 1) ^ 1][x])
                g[i & 1][vas] += g[(i & 1) ^ 1][x];
            else if (w[i & 1][vas] > w[(i & 1) ^ 1][x])
                w[i & 1][vas] = w[(i & 1) ^ 1][x], g[i & 1][vas] = g[(i & 1) ^ 1][x];

            if (w[i & 1][vas + rt] == w[(i & 1) ^ 1][x] + ft)
                g[i & 1][vas + rt] += g[(i & 1) ^ 1][x];
            else if (w[i & 1][vas + rt] > w[(i & 1) ^ 1][x] + ft)
                w[i & 1][vas + rt] = w[(i & 1) ^ 1][x] + ft, g[i & 1][vas + rt] = g[(i & 1) ^ 1][x];

            int v = len[i - 1][0];
            og[v]++, vas += gt[i][pos[v]];

            if (v > of)
                ft++;

            while (og[v] == len[i - 1][v] + 1) {
                vas -= gt[i][pos[v]] * (len[i - 1][v] + 1);

                if (v > of)
                    ft -= (len[i - 1][v] + 1);

                vas += gt[i][pos[v - 1]];

                if (v - 1 > of)
                    ft++;

                og[v] = 0, og[v - 1]++, v--;
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << w[n & 1][i] << " " << g[n & 1][i] << endl;

    return 0;
}