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
#include <cstdio>
#include <cassert>
#include <utility>

#define REP(a, n) for (int a = 0; a < (n); ++a)
#define FOR(a, b, c) for (int a = (b); a <= (c); ++a)

#define INF 1000000000

typedef long long LL;

using namespace std;

//////////////////////

int tab[40], N, k, ile_kodow = 0;
int best[2][1 << 20];
LL rep[2][1 << 20];

void update(int kod, int bst, int rp) {
//    assert(kod < (1 << 20));
    while (ile_kodow <= kod)
        best[k][ile_kodow++] = INF;
    if (bst < best[k][kod]) {
        best[k][kod] = bst;
        rep[k][kod] = rp;
    }
    else
    if (bst == best[k][kod])
        rep[k][kod] += rp;
}

LL unpack(int kod, LL zostaly) {
//    printf("unpack: %d -> ", kod);
    LL bb = 0;
    int cur = 0;
    for (;;) {
        while (zostaly & (1LL << cur))
            ++cur;
        if (cur >= N) {
//            printf("%lld\n", bb);
            return bb;
        }
        // cur to pierwsze zero
        int c2 = cur;
        while (!(zostaly & (1LL << c2)))
            ++c2;
        // c2 to najblizsza jedynka
        int pos = c2 - cur + 1; // ile możliwości
        int ile1 = kod % pos;
        kod /= pos;
        REP(a, ile1)
            bb |= (1LL << (cur + a));
        cur = c2 + 1;
    }
}

pair<int, int> pack(LL bb, LL bb2, LL zostaly) {
//    printf("pack: %lld -> ", bb);
    int kod = 0, kod2 = 0, mnoznik = 1;
    int cur = 0;
    for (;;) {
        while (zostaly & (1LL << cur))
            ++cur;
        if (cur >= N) {
//            printf("%d\n", kod);
            return make_pair(kod, kod2);
        }
        // cur to pierwsze zero
        int c2 = cur;
        while (!(zostaly & (1LL << c2)))
            ++c2;
        // c2 to najblizsza jedynka
        int pos = c2 - cur + 1; // ile możliwości
        int ile1 = 0, ile2 = 0;
        FOR(a, cur, c2 - 1) {
            if (bb & (1LL << a))
                ++ile1;
            if (bb2 & (1LL << a))
                ++ile2;
        }
        kod += ile1 * mnoznik;
        kod2 += ile2 * mnoznik;
        mnoznik *= pos;
        cur = c2 + 1;
    }
}

int main() {
    scanf("%d", &N);
    REP(a, N) {
        scanf("%d", &tab[a]);
        --tab[a];
    }
    LL zostaly = (1LL << (N + 1)) - 1;
    update(0, 0, 1);
    REP(a, N) {
        int prev_ilek = ile_kodow;
        ile_kodow = 0;
        k = !k;
        LL new_zostaly = zostaly & ~(1LL << tab[a]);
        REP(kod, prev_ilek) {
            LL bb = unpack(kod, zostaly);
            int ilew = 0;
            FOR(x, tab[a] + 1, N - 1)
                if (bb & (1LL << x))
                    ++ilew;
            auto kodp = pack(bb, bb | (1LL << tab[a]), new_zostaly);
            update(kodp.first, best[!k][kod], rep[!k][kod]);
            update(kodp.second, best[!k][kod] + ilew, rep[!k][kod]);
            
        }
        zostaly = new_zostaly;
    }
    FOR(a, 1, N)
        printf("%d %lld\n", best[k][a], rep[k][a]);
}