说明

给定一个 $1$ 到 $n$ 的排列 $a_{1..n}$，它有 $2^n-1$ 个非空子序列。

请对于每个 $k$，找到一个长度为 $k$ 的子序列，使得这个子序列的逆序对数量最少，并输出逆序对数量最少的子序列的数量。

输入格式

第一行包含一个正整数 $n$。

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

输出格式

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

5
5 3 1 4 2

0 5
0 3
1 2
3 1
7 1

提示

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