P5972 [PA 2019] Desant

给定一个 $1$ 到 $n$ 的排列 $a_{1..n}$，它有 $2^n-1$ 个非空子序列。 请对于每个 $k$，找到一个长度为 $k$ 的子序列，使得这个子序列的逆序对数量最少，并输出逆序对数量最少的子序列的数量。

第一行包含一个正整数 $n$。 第二行包含 $n$ 个正整数 $a_1,a_2,...,a_n$。

输出 $n$ 行，每行两个整数，第 $k$ 行输出长度为 $k$ 的子序列中逆序对数量的最小值以及满足这个最小值的子序列数量。

对于 $100\%$ 的数据，$1\le k\le n$，$1\le n\le 40$，$1\le a_i\le n,a_i\ne a_j$。