#include <string.h>
#include <stdio.h>

typedef union queue_t {
    struct { int h, t; };
    int q[1000005];
} queue;

typedef struct node_t {
    int fq, l, r;
} node;

int n, m, lg[1000005]; 
long long int cod[1000005];
queue x, y;
node arb[2000010];

inline static void min(int * mnl, int * mnr) {
    if(x.h + 1 <= x.t && arb[x.q[x.h + 1]].fq < arb[*mnr].fq) {
        *mnr = x.q[++x.h]; ++x.h;
    } else if(y.h + 1 <= y.t && arb[y.q[y.h + 1]].fq < arb[*mnl].fq) {
        *mnl = y.q[++y.h]; ++y.h;
    } else {
        ++x.h;
        ++y.h;
    }
}

inline static void dfs(const int p, const long long c, const int l) {
    if(arb[p].l != 0) {
        dfs(arb[p].l, (c << 1) + 1, l + 1);
        dfs(arb[p].r, (c << 1) + 0, l + 1);
    } else {
        lg[p] = l;
        cod[p] = c;
    }
}

int main(void) {
    x.h = 2; x.t = 1;
    y.h = 2; y.t = 1;
    freopen("huffman.in", "r", stdin);
    freopen("huffman.out", "w", stdout);

    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &arb[i + 2].fq);
        x.q[++x.t] = i + 2;
    }

    m = n + 2;
    arb[m].l = x.h++;
    arb[m].r = x.h++;
    arb[m].fq = arb[arb[m].l].fq + arb[arb[m].r].fq;
    y.q[++y.t] = m;

    for(int ll, rr; x.h <= x.t; ) {
        ll = x.q[x.h];
        rr = y.q[y.h];

        min(&ll, &rr);

        ++m;
        arb[m].l = ll;
        arb[m].r = rr;
        arb[m].fq = arb[ll].fq + arb[rr].fq;
        y.q[++y.t] = m;
    }

    for(int ll, rr; y.h < y.t; ) {
        ll = y.q[y.h++];
        rr = y.q[y.h++];
        ++m;
        arb[m].l = ll;
        arb[m].r = rr;
        arb[m].fq = arb[ll].fq + arb[rr].fq;
        y.q[++y.t] = m;
    }

    dfs(m, 0ll, 0);
    for(int i = 0; i < n; ++i) {
        printf("%d %lld\n", lg[i + 2], cod[i + 2]);
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}