P5972 [PA 2019] Desant

Given a permutation $a_{1..n}$ of $1$ to $n$, it has $2^n - 1$ non-empty subsequences. For each $k$, find a subsequence of length $k$ such that the number of inversions in this subsequence is minimal, and output the number of subsequences whose inversion count is minimal.

The first line contains a positive integer $n$. The second line contains $n$ positive integers $a_1, a_2, ..., a_n$.

Output $n$ lines, each containing two integers. On the $k$-th line, output the minimum number of inversions among subsequences of length $k$, and the number of subsequences that achieve this minimum.

For $100\%$ of the testdata, $1 \le k \le n$, $1 \le n \le 40$, $1 \le a_i \le n, a_i \ne a_j$. Translated by ChatGPT 5