多年来，Bitotia 一直在入侵 Byteotia 并掠夺其自然资源和知识产权。然而这一次，轮到 Byteotia 入侵狡猾的 Bitotia 了。这次精心策划的入侵的第一步是对 Bitobytian 海滩的突袭。

为了保持隐蔽，Byteforce 精锐部队中将有 $k$ 名成员被派往海滩。目前 Byteforce 由 $n$ 名士兵组成，编号为 $1$ 到 $n$。编号为 $i$ 的士兵近战技能等级为 $i$，远程战斗技能等级为 $a_i$。序列 $a_1, \dots, a_n$ 是 $1$ 到 $n$ 的一个排列。技能等级越高，士兵在相应领域就越强。

众所周知，在一支训练有素的部队中，每个人都应该知道自己可以向谁下达命令，以及应该听从谁的命令。如果在参与入侵的士兵中，存在两名士兵 $i$ 和 $j$，满足 $i < j$ 且 $a_i > a_j$，那么他们很可能会因为谁更重要而发生争执。我们称这样的一对士兵为“糟糕的组合”（bad pair）。

我们希望避免此类争执，因此想要最小化士兵中“糟糕的组合”的数量。你需要确定在 $n$ 名士兵中恰好选择 $k$ 名士兵时，所能得到的“糟糕的组合”的最小数量。此外，你还需要确定有多少种选择方式可以达到这个最小数量。

最后，目前尚未决定派往 Bitobytian 海滩的士兵人数。你需要针对从 $1$ 到 $n$ 的每一个 $k$，确定上述两个数值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 40$)，表示 Byteforce 中的士兵人数。

第二行包含 $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) 中的一对，以确保没有争执。

如果想派遣三名士兵，最小的“糟糕的组合”数量为 1，我们可以通过选择 (2, 3, 4) 或 (3, 4, 5) 这两组三人组合来实现。

如果想派遣四名士兵，我们应该选择除第一名士兵之外的所有人，因为第一名士兵虽然近战最差，但远程战斗最强（因为 $a_1 = 5$），所以他会与任何其他士兵产生争执。

如果派遣全部五名士兵，将会有七个“糟糕的组合”。