D. 建造基地

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

你作为第一批科研人员,提前来到了 \beta 星建造基地。

\beta 星盛产锰钛矿石。基地需要一些高度相同的柱子,而每根柱子都需要由恰好两根锰钛矿石顺次连接组成。例如,若你有两根高度分别为 h_x,h_y 的锰钛矿石,那么你可以用两者合成为一根高度为 h_x+h_y 的柱子。每根锰钛矿石显然至多被使用一次

现在你来到了 \beta 星的锰钛矿场,摆在你面前的是 n 根高度分别为 h_i 的锰钛矿石。经过严密思考后你发现,房屋的牢固程度应该取决于柱子的数目,而不是柱子的高度。所以你想知道,使用面前这 n 根矿石最多可以建造出多少根高度相同的柱子?

但小花觉得这个问题太 easy 了,于是 ta 选择多问你一嘴:假设柱子高度均为 h ,基地最多可以建出 \mathrm{res} 根柱子,那么在柱子数目同为 \mathrm{res} h 可以有几种不同的取值?

输入格式

输入格式

输入共两行。

第一行共一个正整数 n ,表示锰钛矿石的数量。

第二行共 n 个正整数 h_i ,含义见题目描述。

输出格式

输出格式

输出共一行两个整数 \mathrm{res} \mathrm{ans} ,分别表示最多的柱子数目以及最优答案下有多少种不同的高度方案。

样例

样例 #1

样例输入 #1

4
4 7 6 5

样例输出 #1

2 1

样例 #2

样例输入 #2

6
1 1000 100 1500 10 1800

样例输出 #2

1 15

数据范围与提示

对于 20\% 的数据, 1\leq n\leq 100

对于 40\% 的数据, 1\leq n \leq 10^3

对于 70\% 的数据, 1\leq n\leq 10^5

对于 100\% 的数据, 1\leq n\leq 10^6 1\leq h_i \leq 3\times 10^3