#3217. 「PA 2019」Desant

标签: 传统 | 时间限制: 6000 ms | 内存限制: 768 MiB |

题目描述

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

输出

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