#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 45, INF = 1e9;

int n;
int A[MAX_N];
int leftSize;
int rightSize;
pair<int, long long> tree[(1 << 21) + 5][22];
int dodaj[(1 << 21) + 5];
int pietro[(1 << 21) + 5];
vector<int> taken;
int whereIs[MAX_N];
int lastNode[MAX_N];

int countInversions() {
    int ret = 0;
    for (int i = 0; i < taken.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (whereIs[taken[j]] > whereIs[taken[i]]) {
                ret++;
            }
        }
    }
    return ret;
}

std::function<pair<int, long long>(pair<int, long long> a, pair<int, long long> b) > Merge;

void buildTree(const vector<int>& right, int pos, int w, int inversions) {
    // cerr << right.size() << " " << pos << " " << w << endl;
    if (pos >= 0) {
        lastNode[pos] = max(lastNode[pos], w);
    }
    if (pos == (int)right.size() - 1) {
        tree[w][taken.size()] = {inversions, 1};
//         cerr << "buildLeaf: " << w << " " << taken.size() << " " << countInversions() << " " << 1 << endl;
        return;
    }
    
    buildTree(right, pos + 1, 2 * w, inversions);
    for (int i = 0; i < taken.size(); i++) {
        if (whereIs[taken[i]] > whereIs[right[pos + 1]]) {
            inversions++;
        }
    }
    taken.push_back(right[pos + 1]);
    buildTree(right, pos + 1, 2 * w + 1, inversions);
    taken.pop_back();
//     cerr << "buildNode: " << w << endl;
    for (int k = 0; k <= rightSize; k++) {
        tree[w][k] = Merge(tree[2 * w][k], tree[2 * w + 1][k]);
//         cerr << "(" << tree[w][k].first << ", " << tree[w][k].second << "), ";
    }
//     cerr << endl;
}

pair<int, long long> best[MAX_N];
int biggest[MAX_N];
bool swappedd;


// template<class T>
// std::function<T(T a, T b)> lambda = (swappedd ? max<T> : min<T>);

void addInversions(int w, int c) {
    int max_nodes = (1 << (rightSize + 1));
    
    for (int i = w; i > 1; i--) {
        if (i % 2 == 1) {
            dodaj[i] += c;
        }
        int maxSize = rightSize - pietro[i] + __builtin_popcount(i);
        for (int k = 0; k < maxSize; k++) {
            if (2 * i + 1 < max_nodes) {
                if (swappedd) {
                    tree[i][k] = max(tree[2 * i][k], tree[2 * i + 1][k]);
                } else {
                    tree[i][k] = min(tree[2 * i][k], tree[2 * i + 1][k]);
                }
                if (tree[2 * i][k].first == tree[2 * i + 1][k].first) {
                    tree[i][k].second = tree[2 * i][k].second + tree[2 * i + 1][k].second;
                }
//                 tree[i][k] = Merge(tree[2 * i][k], tree[2 * i + 1][k]);
                tree[i][k].first += dodaj[i];
            } else {
                if (i % 2 == 1) {
                    tree[i][k].first += c;
                }
            }
        }
    }
    for (int k = 0; k <= rightSize; k++) {
        tree[1][k] = Merge(tree[2][k], tree[3][k]);
    }
}

void solve(const vector<int>& left, int pos, int inversions) {
    if (pos == left.size()) {
        for (int k = taken.size(); k <= min(rightSize + (int)taken.size(), n); k++) {
            auto p = tree[1][k - taken.size()];
//             cerr << "SOLVE " << pos << " " << taken.size() << " " << inversions << " " << w << " " << k << " " << p.first << " " << p.second << endl;
            best[k] = Merge(best[k], {p.first + inversions, p.second});
//             cerr << k << " " << best[k].first << endl;
        }
        return;
    }
    
//     cerr << "solve: " << pos << " " << inversions << " " << biggest[pos] << " " << lastNode[biggest[pos]] << endl;
    
    solve(left, pos + 1, inversions);
    
    for (int x : taken) {
        if (whereIs[x] < whereIs[left[pos]]) {
            inversions++;
        }
    }
    // cerr << pos << " " << inversions << endl;
    taken.push_back(left[pos]);
    addInversions(lastNode[biggest[pos]], 1);
    solve(left, pos + 1, inversions);
    addInversions(lastNode[biggest[pos]], -1);
    taken.pop_back();
}

void meetInTheMiddle(vector<int> left, vector<int> right, bool swapped) {
//     cerr << "swapped " << swapped << endl;
    if (swapped) {
        
        for (int i = 1; i < (1 << (rightSize + 1)); i++) {
            for (int k = 0; k <= rightSize; k++) {
                tree[i][k] = {-1e9, 0};
            }
        }
        for (int k = 0; k <= n; k++) {
            best[k] = {-1e9, 0};
        }
        Merge = [](auto a, auto b) {
            if (a.first != b.first) {
                return max(a, b);
            } else {
                return make_pair(a.first, a.second + b.second);
            }
        };
    } else {
        for (int i = 1; i < (1 << (rightSize + 1)); i++) {
            for (int k = 0; k <= rightSize; k++) {
                tree[i][k] = {1e9, 0};
            }
        }
        for (int k = 0; k <= n; k++) {
            best[k] = {1e9, 0};
        }
        Merge = [](auto a, auto b) {
            if (a.first != b.first) {
                return min(a, b);
            } else {
                return make_pair(a.first, a.second + b.second);
            }
        };
    }
    auto sortedLeft = left;
    sort(sortedLeft.begin(), sortedLeft.end());
    reverse(sortedLeft.begin(), sortedLeft.end());
    auto sortedRight = right;
    sort(sortedRight.begin(), sortedRight.end());
    
    buildTree(sortedRight, -1, 1, 0);
    
    for (int i = 0; i < sortedLeft.size(); i++) {
        biggest[i] = sortedRight.size();
        if (sortedRight.empty() || sortedRight[0] > sortedLeft[i]) {
            continue;
        }
        for (int j = 0; j < sortedRight.size(); j++) {
            if (j == (int)sortedRight.size() - 1 || (sortedRight[j] < sortedLeft[i] && sortedRight[j + 1] > sortedLeft[i])) {
                biggest[i] = j;
                break;
            }
        }
    }
    
    solve(sortedLeft, 0, 0);
    
    for (int k = 0; k <= n; k++) {
        if (swapped) {
//             cerr << k << " " << best[k].first << endl;
            best[k].first = k * (k - 1) / 2 - best[k].first;
        }
    }
}

int main() {
    scanf("%d", &n);
   
    for (int i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
    }
    
    int mid = n / 2;
    vector<int> left;
    vector<int> right;
    for (int i = 1; i <= mid; i++) {
        left.push_back(A[i]);
    }
    
    for (int i = mid + 1; i <= n; i++) {
        right.push_back(A[i]);
    }
  
    int inversions = 0;
    for (auto x : left) {
        for (auto y : right) {
            if (x > y) {
                inversions++;
            }
        }
    }
    
    bool swapped = false;
    if (inversions > left.size() * right.size() - inversions) {
        swap(left, right);
        reverse(left.begin(), left.end());
        reverse(right.begin(), right.end());
        swapped = true;
    }
    swappedd = swapped;
    leftSize = left.size();
    rightSize = right.size();
    
    for (int i = 0; i < left.size(); i++) {
        whereIs[left[i]] = i;
    }
    
    for (int i = 0; i < right.size(); i++) {
        whereIs[right[i]] = i;
    }
    
    // cerr << "Whereis:\n";
    for (int i = 0; i < left.size(); i++) {
        // cerr << left[i] << " " << whereIs[left[i]] << endl;
    }
    
    for (int i = 2; i <= (1 << (rightSize + 1)); i++) {
        pietro[i] = pietro[i / 2] + 1;
    }
    
    meetInTheMiddle(left, right, swapped);
  
    for (int k = 1; k <= n; k++) {
        printf("%d %lld\n", best[k].first, best[k].second);
    }
    
    return 0;
}