Desant

题目描述

题目译自 PA 2019 Runda 2 Desant

给定一个 $1$ 到 $n$ 的排列 $a_1, a_2, \dots, a_n$，它有 $2^n - 1$ 个非空子序列。

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

输入格式

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

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

输出格式

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

样例

输入

5
5 3 1 4 2

输出

0 5
0 3
1 2
3 1
7 1

数据范围与提示

对于 $100\%$ 的数据，保证 $1 \le n \le 40$，$1 \le a_i \le n$ 且 $a_i$ 互不相同。