多年来，比托齐亚（Bitocja）经常入侵巴伊托齐亚（Bajtocja），掠夺其自然资源和知识财富。这一次，巴伊托齐亚人将反击狡诈的比托齐亚人。这一精心策划的战略的第一步是对比托巴伊坦（Bitobajtan）海滩进行登陆作战。

行动必须隐秘，因此将派遣一支由恰好 $k$ 名巴伊托格罗姆（Bajtogrom）精英部队成员组成的部队前往海滩。目前，部队中有 $n$ 名士兵，我们用从 $1$ 到 $n$ 的自然数对他们进行编号。编号为 $i$ 的士兵近战水平为 $i$，远程战斗水平为 $a_i$。序列 $a_1, \dots, a_n$ 是 $1$ 到 $n$ 的一个排列。水平越高，士兵在该领域的造诣就越深。

众所周知，在优秀的特种部队中，每个人都应该知道该听从谁的指挥，以及可以指挥谁。如果同时派遣两名编号分别为 $i$ 和 $j$ 的士兵，且满足 $i < j$ 且 $a_i > a_j$，那么他们之间可能会发生所谓的“冲突”，即他们会因为争论谁在巴伊托格罗姆的行列中地位更高而发生争吵。

在选择 $k$ 名士兵进行登陆时，必须尽可能减少可能发生冲突的士兵对的数量。你的任务是求出这个最小的冲突对数。此外，你还需要求出有多少种选择 $k$ 名士兵的方法可以达到这个最小值。

还有一件事。目前还不确定到底要派遣多少名士兵前往比托巴伊坦海滩。因此，请针对每一个 $k$（从 $1$ 到 $n$），计算出上述两个数值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 40$)，表示巴伊托格罗姆部队中的士兵人数。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le n, a_i \neq a_j$ 当 $i \neq j$)，其中 $a_i$ 描述了第 $i$ 名士兵的远程战斗水平。

输出格式

输出应包含 $n$ 行，每行包含两个整数。

第 $k$ 行的两个数字应分别表示：如果我们要派遣恰好 $k$ 名士兵进行登陆，可能发生冲突的士兵对的最小数量，以及达到该最小值的方案数。

样例

样例输入 1

5
5 3 1 4 2

样例输出 1

0 5
0 3
1 2
3 1
7 1

说明

如果我们要派遣一名士兵，显然没有人会发生冲突，且该士兵有五种选择方式。

如果我们要派遣两名士兵，必须选择 (2, 4)、(3, 4) 或 (3, 5) 中的某一对，以确保不会发生冲突。

如果我们要派遣三名士兵，可以通过派遣 (2, 3, 4) 或 (3, 4, 5) 的部队，使冲突对数达到最小（即 1 对）。

如果我们要派遣四名士兵，最优方案是派遣除第一名士兵之外的所有人。第一名士兵不仅近战最差（因为编号为 1），而且远程战斗水平最高（因为 $a_1 = 5$），这导致他与任何其他士兵都可能发生冲突。

如果我们要派遣全部五名士兵，则共有七对士兵可能发生冲突。