← 返回题目列表

Codeforces · 1216/D

D. 剑

中文机器翻译题面 查看原题

剧院地下室里有$$$n$$$种在演出期间使用过的剑。而且每种类型的剑都有$$$x$$$。 $$$y$$$人们闯入了剧院地下室,他们每个人都拿走了某种单一类型的$$$z$$$剑。请注意,不同的人可能会使用不同类型的剑。请注意,值 $$$x、y$$$ 和 $$$z$$$ 对您来说是未知的。

第二天早上,剧院导演发现了损失。他清点了所有剑——恰好 $$$a_i$$$ 类型的第 $$$i$$$ 剑未被触及。

对于地下室中每种类型的剑的初始数量、闯入地下室的人数以及每人拿走了多少把剑,导演一无所知。

例如,如果 $$$n=3$$$、$$$a = [3, 12, 6]$$$,则可能的情况之一是 $$$x=12$$$、$$$y=5$$$ 和 $$$z=3$$$。然后前三人拿的是第一式剑,另外两人拿的是第三式剑。请注意,您事先不知道 $$$x、y$$$ 和 $$$z$$$ 的值,但知道 $$$n$$$ 和 $$$a$$$ 的值。

因此他寻求你的帮助。确定可以闯入剧院地下室的最少人数$$$y$$$,以及每个人拿走的剑$$$z$$$ 的数量。

输入

输入的第一行包含一个整数 $$$n$$$ $$$(2 \le n \le 2 \cdot 10^{5})$$$ — 剑的类型数量。

输入的第二行包含序列 $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \le 10^{9})$$$,其中 $$$a_i$$$ 等于盗窃后留在地下室的第 $$$i$$$ 类型的剑的数量。保证至少存在一对这样的索引 $$$(j, k)$$$ 使得 $$$a_j \neq a_k$$$ 。

输出

打印两个整数 $$$y$$$ 和 $$$z$$$ — 可以闯入地下室的最少人数以及每个人拿走的剑数。

示例

输入 #1

3
3 12 6

输出 #1

5 3

输入 #2

2
2 9

输出 #2

1 7

输入 #3

7
2 1000000000 4 6 8 4 2

输出 #3

2999999987 2

输入#4

6
13 52 0 13 26 52

输出#4

12 13

注意

在第一个示例中,$$$y$$$ 的最小值等于 $$$5$$$,即可以闯入地下室的最少人数为 $$$5$$$。他们每个人都拿了$$$3$$$剑:其中三个人拿了第一种类型的$$$3$$$剑,另外两个人拿了第三种类型的$$$3$$$剑。

在第二个示例中,$$$y$$$ 的最小值为 $$$1$$$,即可以闯入地下室的最少人数等于 $$$1$$$。他拿走了$$$7$$$第一类剑。