题目描述

我们讲一个悲伤的故事。

从前有一个贫穷的樵夫在河边砍柴。

这时候河里出现了一个水神，夺过了他的斧头，说：

“这把斧头，是不是你的？”

樵夫一看：“是啊是啊！”

水神把斧头扔在一边，又拿起一个东西问：

“这把斧头，是不是你的？”

樵夫看不清楚，但又怕真的是自己的斧头，只好又答：“是啊是啊！”

水神又把手上的东西扔在一边，拿起第三个东西问：

“这把斧头，是不是你的？”

樵夫还是看不清楚，但是他觉得再这样下去他就没法砍柴了。

于是他又一次答：“是啊是啊！真的是！”

水神看着他，哈哈大笑道：

“你看看你现在的样子，真是丑陋！”

之后就消失了。

樵夫觉得很坑爹，他今天不仅没有砍到柴，还丢了一把斧头给那个水神。

于是他准备回家换一把斧头。

回家之后他才发现真正坑爹的事情才刚开始。

水神拿着的的确是他的斧头。

但是不一定是他拿出去的那把，还有可能是水神不知道怎么偷偷从他家里拿走的。

换句话说，水神可能拿走了他的一把，两把或者三把斧头。

樵夫觉得今天真是倒霉透了，但不管怎么样日子还得过。

他想统计他的损失。

樵夫的每一把斧头都有一个价值，不同斧头的价值不同。总损失就是丢掉的斧头价值和。

他想对于每个可能的总损失，计算有几种可能的方案。

注意：如果水神拿走了两把斧头 $a$ 和 $b$，$(a,b)$ 和 $(b,a)$ 视为一种方案。拿走三把斧头时，$(a,b,c)$，$(b,c,a)$，$(c,a,b)$，$(c,b,a)$，$(b,a,c)$，$(a,c,b)$ 视为一种方案。

输入格式

第一行是整数 $n$，表示有 $n$ 把斧头。
接下来 $n$ 行升序输入 $n$ 个数字 $a_i$，表示每把斧头的价值。

输出格式

若干行，按升序对于所有可能的总损失值与方案数输出。 具体地，每一行包含两个正整数 $x,y$，$x$ 为损失值，$y$ 为方案数。

4
4
5
6
7

4 1
5 1
6 1
7 1
9 1
10 1
11 2
12 1
13 1
15 1
16 1
17 1
18 1

样例解释

$11$ 有两种方案是 $4+7$ 和 $5+6$，其他损失值都有唯一方案，例如 $4=4,5=5,10=4+6,18=5+6+7$。

数据规模与约定

对于 $100\%$ 的数据，$n,a_i \le 4 \times 10^4$。