Description

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.

Input Format

The first line contains a positive integer $n$.

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

Output Format

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.

5
5 3 1 4 2

0 5
0 3
1 2
3 1
7 1

Hint

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