#3217. 「PA 2019」Desant

内存限制:768 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 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

数据范围与提示

1 \le n \le 40, 1 \le a_i \le n, a_i \ne a_j